A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows

  • 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 ongo- ing 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andrea Bettinelli, Alberto Ceselli, Giovanni Righini
DOI:https://doi.org/10.1007/s12532-014-0064-0
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2014
Tag:Software
Volume:6
Issue:2
Page Number:27
First Page:171
Last Page:197
Mathematical Programming Computation :MPC 2014 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.