The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Masalah pikap dan penghantaran (PDP) meminta untuk mencari satu set kenderaan yang menyediakan set permintaan tertentu dengan kos perjalanan minimum, di mana setiap permintaan terdiri daripada tempat pengambilan, tempat penghantaran dan muatan (kuantiti untuk dihantar dari tempat pengambilan ke tempat penghantaran). Dalam masalah pengambilan dan penghantaran dengan pemindahan (PDPT), bagi setiap permintaan, muatannya yang diambil di tempat pengambilan dibenarkan untuk diturunkan di tempat pemindahan sebelum ia diambil semula dan dihantar ke tempat penghantaran oleh kenderaan lain. Kertas kerja ini menganalisis kos perjalanan maksimum yang boleh dijimatkan dengan memperkenalkan titik pemindahan penghantaran kepada masalah pengambilan dan penghantaran (PDP). Kami menunjukkan bahawa sempadan adalah berkadaran dengan punca kuasa dua bilangan kitaran dalam penyelesaian PDPT optimum dan juga punca kuasa dua bilangan permintaan. Selain itu, kami membentangkan contoh yang terikat adalah ketat untuk kes khas.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Yoshitaka NAKAO, Hiroshi NAGAMOCHI, "Worst Case Analysis for Pickup and Delivery Problems with Transfer" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2328-2334, September 2008, doi: 10.1093/ietfec/e91-a.9.2328.
Abstract: The pickup and delivery problem (PDP) asks to find a set of vehicles that serve a given set of requests with the minimum travel cost, where each request consists of a pickup point, a delivery point and a load (the quantity to be delivered from the pickup point to the delivery point). In the pickup and delivery problem with transfer (PDPT), for each request, its load picked up at the pickup point is allowed to be dropped at a transshipment point before it is picked up again and delivered to the delivery point by another vehicle. This paper analyzes the maximum travel cost that can be saved by introducing a transshipment point to the pickup and delivery problem (PDP). We show that the bounds are in proportion to square root of the number of cycles in an optimal PDPT solution and also square root of the number of requests. We furthermore present an instance that the bound is the tight for a special case.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2328/_p
Salinan
@ARTICLE{e91-a_9_2328,
author={Yoshitaka NAKAO, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Worst Case Analysis for Pickup and Delivery Problems with Transfer},
year={2008},
volume={E91-A},
number={9},
pages={2328-2334},
abstract={The pickup and delivery problem (PDP) asks to find a set of vehicles that serve a given set of requests with the minimum travel cost, where each request consists of a pickup point, a delivery point and a load (the quantity to be delivered from the pickup point to the delivery point). In the pickup and delivery problem with transfer (PDPT), for each request, its load picked up at the pickup point is allowed to be dropped at a transshipment point before it is picked up again and delivered to the delivery point by another vehicle. This paper analyzes the maximum travel cost that can be saved by introducing a transshipment point to the pickup and delivery problem (PDP). We show that the bounds are in proportion to square root of the number of cycles in an optimal PDPT solution and also square root of the number of requests. We furthermore present an instance that the bound is the tight for a special case.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2328},
ISSN={1745-1337},
month={September},}
Salinan
TY - JOUR
TI - Worst Case Analysis for Pickup and Delivery Problems with Transfer
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2328
EP - 2334
AU - Yoshitaka NAKAO
AU - Hiroshi NAGAMOCHI
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2328
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - The pickup and delivery problem (PDP) asks to find a set of vehicles that serve a given set of requests with the minimum travel cost, where each request consists of a pickup point, a delivery point and a load (the quantity to be delivered from the pickup point to the delivery point). In the pickup and delivery problem with transfer (PDPT), for each request, its load picked up at the pickup point is allowed to be dropped at a transshipment point before it is picked up again and delivered to the delivery point by another vehicle. This paper analyzes the maximum travel cost that can be saved by introducing a transshipment point to the pickup and delivery problem (PDP). We show that the bounds are in proportion to square root of the number of cycles in an optimal PDPT solution and also square root of the number of requests. We furthermore present an instance that the bound is the tight for a special case.
ER -