A compact arc-based ILP formulation for the pickup and delivery problem with divisible pickups and deliveries
| Autor: | Bolor Jargalsaikhan, Ward Romeijnders, Kees Jan Roodbergen |
|---|---|
| Přispěvatelé: | Research programme OPERA |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
050210 logistics & transportation
Mathematical optimization 021103 operations research Integer Linear Program Computer science 05 social sciences 0211 other engineering and technologies Transportation 02 engineering and technology Arc (geometry) Divisible Pickups and Deliveries 0502 economics and business Single vehicle Pickup Pickup and Delivery Problem Integer programming Civil and Structural Engineering |
| Zdroj: | Transportation Science, 55(2), 336-352. INFORMS |
| ISSN: | 0041-1655 |
| Popis: | We consider the capacitated single vehicle one-to-one pickup and delivery problem with divisible pickups and deliveries (PDPDPD). In this problem, we do not make the standard assumption of one-to-one pickup and delivery problems (PDPs) that each location has only one transportation request. Instead we assume there are multiple requests per location that may be performed individually. This may result in multiple visits to a location. We provide a new compact arc-based integer linear programming (ILP) formulation for the PDPDPD by deriving time-consistency constraints that identify the order in which selected outgoing arcs from a node are actually traversed. The formulation can also easily be applied to the one-to-one PDP by restricting the number of times that a node can be visited. Numerical results on standard one-to-one PDP test instances from the literature show that our compact formulation is almost competitive with tailor-made solution methods for the one-to-one PDP. Moreover, we observe that significant cost savings of up to 15% on average may be obtained by allowing divisible pickups and deliveries in one-to-one PDPs. It turns out that divisible pickups and deliveries are not only beneficial when the vehicle capacity is small, but also when this capacity is unrestrictive. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|