Paper Info
Title
A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows.
Abstract
The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongoing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.
Year
DOI
Venue
2014
10.1007/mpc.v0i0.140
Math. Program. Comput.
Keywords
Field
DocType
90C27, 90C90, 90B06, 65K05
Dynamic programming,Mathematical optimization,Vehicle routing problem,Branch and price,Algorithm,Operations research,Exploit,Logistics management,Pickup,General partnership,Mathematics,Economies of scale
Journal
Volume
Issue
ISSN
6
2
1867-2957
Citations 
PageRank 
References 
2
0.36
18
Authors
3
Name
Order
Citations
PageRank
Andrea Bettinelli1193.43
Alberto Ceselli234130.53
Giovanni Righini352033.90