A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations

Autor: Martin W. P. Savelsbergh, Gizem Ozbaygin, Hande Yaman, Oya Ekin Karasan
Rok vydání: 2017
Předmět:
Engineering
spatial analysis
Operations research
transportation economics
Location
Computational studies
0211 other engineering and technologies
Transportation
Routing algorithms
02 engineering and technology
Management Science and Operations Research
Vehicle Routing Problems
Travelling salesman problem
Transport engineering
travel behavior
0502 economics and business
Vehicle routing problem
Resource-constrained shortest path
Branch-and-price
Branch-and-price algorithms
Computational results
Average cost
Civil and Structural Engineering
Constrained shortest path
050210 logistics & transportation
algorithm
021103 operations research
business.industry
Branch and price
05 social sciences
Vehicles
Integer programming
Vehicle routing
Sales
Costs
Trunk delivery
freight transport
travel time
Test set
Shortest path problem
Fleet operations
Capacitated vehicles
Roaming
Routing (electronic design automation)
business
Roaming delivery locations
Zdroj: Transportation Research Part B: Methodological
ISSN: 0191-2615
DOI: 10.1016/j.trb.2017.02.003
Popis: We study the vehicle routing problem with roaming delivery locations in which the goal is to find a least-cost set of delivery routes for a fleet of capacitated vehicles and in which a customer order has to be delivered to the trunk of the customer's car during the time that the car is parked at one of the locations in the (known) customer's travel itinerary. We formulate the problem as a set-covering problem and develop a branch-and-price algorithm for its solution. The algorithm can also be used for solving a more general variant in which a hybrid delivery strategy is considered that allows a delivery to either a customer's home or to the trunk of the customer's car. We evaluate the effectiveness of the many algorithmic features incorporated in the algorithm in an extensive computational study and analyze the benefits of these innovative delivery strategies. The computational results show that employing the hybrid delivery strategy results in average cost savings of nearly 20% for the instances in our test set. © 2017 Elsevier Ltd
Databáze: OpenAIRE
Externí odkaz: