The vehicle routing problem with simultaneous pickup and delivery and handling costs
| Autor: | Richard P. Hornstra, Kees Jan Roodbergen, Leandro C. Coelho, Allyson Silva |
|---|---|
| Přispěvatelé: | Research programme OPERA |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Service (systems architecture) General Computer Science Computer science Heuristic (computer science) 0211 other engineering and technologies 02 engineering and technology LARGE NEIGHBORHOOD SEARCH Management Science and Operations Research Pickup and delivery Travelling salesman problem HEURISTICS 020901 industrial engineering & automation Vehicle routing problem Pickup Hybrid heuristic ALGORITHM Metaheuristic 021103 operations research Handling policies Heuristic TIME WINDOWS METAHEURISTICS LOGISTICS SINGLE Modeling and Simulation TRAVELING SALESMAN PROBLEM Benchmark (computing) Heuristics |
| Zdroj: | Computers & Operations Research, 115:104858. PERGAMON-ELSEVIER SCIENCE LTD |
| ISSN: | 0305-0548 |
| Popis: | In this paper we introduce the vehicle routing problem with simultaneous pickup and delivery and handling costs (VRPSPD-H). In the VRPSPD-H, a fleet of vehicles operates from a single depot to service all customers, which have both a delivery and a pickup demand such that all delivery items originate from and all pickup items go to the depot. The items on the vehicles are organized as a single linear stack where only the last loaded item is accessible. Handling operations are required if the delivery items are not the last loaded ones. We implement a heuristic handling policy approximating the optimal decisions for the handling sub-problem, and we propose two bounds on the optimal policy, resulting in two new myopic policies. We show that one of the myopic policies outperforms the other one in all configurations, and that it is competitive with the heuristic handling policy if many routes are required. We propose an adaptive large neighborhood search (ALNS) metaheuristic to solve our problem, in which we embed the handling policies. Computational results indicate that our metaheuristic finds optimal solutions on instances of up to 15 customers. We also compare our ALNS metaheuristic against best solutions on benchmark instances of two special cases, the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) and the traveling salesman problem with pickups, deliveries and handling costs (TSPPD-H), and on two related problems, the vehicle routing problem with divisible pickup and delivery (VRPDPD) and the vehicle routing problem with mixed pickup and delivery (VRPMPD). We find or improve 39 out of 54 best known solutions (BKS) for the VRPSPD, 36 out of 54 BKS for the VRPDPD, 15 out of 21 BKS for the VRPMPD, and 69 out of 80 BKS for the TSPPD-H. Finally, we introduce and analyze solutions for the variations of the VRPDPD and VRPMPD with handling costs – the VRPDPD-H and the VRPMPD-H, respectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect