Abstract
We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the Branch-and-Cut-and-Price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness.
Original language | English |
---|---|
Pages (from-to) | 824-839 |
Number of pages | 16 |
Journal | European Journal of Operational Research |
Volume | 279 |
Issue number | 3 |
Early online date | 28 Jun 2019 |
DOIs | |
Publication status | Published - 16 Dec 2019 |
Funding
This work was partially funded by the Discovery Grant and the Discovery Accelerator Supplements programs of the Natural Science and Engineering Research Council of Canada, and the Strategic Clusters program of the fonds québécois de la recherche sur la nature et les technologies. This research is also based upon work supported by the Air Force Office of Scientific Research under award numbers FA9550-17-1-0025 and FA9550-17-1-0234 . During this project, the third author was Adjunct Professor with the Computer Science and Operations Research Department, Université de Montréal. Finally, the authors thank Dr. Phuong Khanh Nguyen for fruitful discussion on the topic. Appendix A
Funders | Funder number |
---|---|
Computer Science and Operations Research Department, Universit? | |
Natural Science and Engineering Research Council of Canada | |
Air Force Office of Scientific Research | FA9550-17-1-0025, FA9550-17-1-0234 |
Fonds Québécois de la Recherche sur la Nature et les Technologies |
Keywords
- Bi-directional dynamic programming
- Branch-and-Cut-and-Price
- Routing
- Separate Pickup and Delivery Problem