Worst Case Analysis for Pickup and Delivery Problems with Transfer
-
- NAKAO Yoshitaka
- Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
-
- NAGAMOCHI Hiroshi
- Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University The Institute of Electronics, Information and Communication Engineers
Search this article
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.
Journal
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91-A (9), 2328-2334, 2008
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390282681288308352
-
- NII Article ID
- 10026851402
-
- NII Book ID
- AA10826239
-
- ISSN
- 17451337
- 09168508
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed