The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2328-2334

- Publication Date
- 2008/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1093/ietfec/e91-a.9.2328

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

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.

Copy

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

Copy

@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},}

Copy

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 -