Pickup and delivery problem with split demand and transfers

Jan Pelikán

Kybernetika (2013)

  • Volume: 49, Issue: 5, page 755-764
  • ISSN: 0023-5954

Abstract

top
We deal with a logistic problem motivated by a case study from a company dealing with inland transportation of piece goods in regular cycles. The problem consists in transportation of goods among regional centres – hubs of a network. Demands on transportation are contained in a matrix of flows of goods between pairs of hubs. The transport is performed by vehicles covering the shipping demands and the task is to design a cyclical route and to place a depot for each vehicle. The route depot can be placed in any hub of the route. Goods can be transferred from one route and vehicle to another route and vehicle. The aim is to minimize the total transportation cost. The task is classified as a new case of the pickup and delivery problem with split demand and transfers (SDPDPT). We propose a mathematical model and prove NP-hardness of the problem. We study demand reducibility. We also deal with skip pickup and delivery problem as a special case and show its complexity.

How to cite

top

Pelikán, Jan. "Pickup and delivery problem with split demand and transfers." Kybernetika 49.5 (2013): 755-764. <http://eudml.org/doc/260575>.

@article{Pelikán2013,
abstract = {We deal with a logistic problem motivated by a case study from a company dealing with inland transportation of piece goods in regular cycles. The problem consists in transportation of goods among regional centres – hubs of a network. Demands on transportation are contained in a matrix of flows of goods between pairs of hubs. The transport is performed by vehicles covering the shipping demands and the task is to design a cyclical route and to place a depot for each vehicle. The route depot can be placed in any hub of the route. Goods can be transferred from one route and vehicle to another route and vehicle. The aim is to minimize the total transportation cost. The task is classified as a new case of the pickup and delivery problem with split demand and transfers (SDPDPT). We propose a mathematical model and prove NP-hardness of the problem. We study demand reducibility. We also deal with skip pickup and delivery problem as a special case and show its complexity.},
author = {Pelikán, Jan},
journal = {Kybernetika},
keywords = {pickup and delivery problem; case study; integer programming; skip transportation; pickup and delivery problem; case study; integer programming; skip transportation},
language = {eng},
number = {5},
pages = {755-764},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Pickup and delivery problem with split demand and transfers},
url = {http://eudml.org/doc/260575},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Pelikán, Jan
TI - Pickup and delivery problem with split demand and transfers
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 5
SP - 755
EP - 764
AB - We deal with a logistic problem motivated by a case study from a company dealing with inland transportation of piece goods in regular cycles. The problem consists in transportation of goods among regional centres – hubs of a network. Demands on transportation are contained in a matrix of flows of goods between pairs of hubs. The transport is performed by vehicles covering the shipping demands and the task is to design a cyclical route and to place a depot for each vehicle. The route depot can be placed in any hub of the route. Goods can be transferred from one route and vehicle to another route and vehicle. The aim is to minimize the total transportation cost. The task is classified as a new case of the pickup and delivery problem with split demand and transfers (SDPDPT). We propose a mathematical model and prove NP-hardness of the problem. We study demand reducibility. We also deal with skip pickup and delivery problem as a special case and show its complexity.
LA - eng
KW - pickup and delivery problem; case study; integer programming; skip transportation; pickup and delivery problem; case study; integer programming; skip transportation
UR - http://eudml.org/doc/260575
ER -

References

top
  1. Archetti, C., Mansini, R., Speranza, M. G., 10.1287/trsc.1030.0084, Transport. Sci. 39 (2005), 182-187. DOI10.1287/trsc.1030.0084
  2. Berbeglia, G., Cordeau, J., Gribkovskaia, L., Laporte, G., Static Pickup and Delivery Problems: A Classification Scheme and Survey., http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.7359, 2007. Zbl1121.90001MR2322153
  3. Fábry, J., Optimization of routes in pickup and delivery problem., In: Mathematical Methods in Economics, University of South Bohemia České Budějovice 2010, pp. 128-131. 
  4. Korte, B., Vygen, J., Combinatorial Optimization., Springer, New York 2002. Zbl1250.90074MR1897297
  5. Savelsbergh, M. W. P., Sol, M., The general pickup and delivery problem., Transport. Res. 29 (1995), 17-29. Zbl0826.90049
  6. Thangiah, S. R., Fergany, A., Salman, A., 10.1007/s10100-007-0035-x, Central Europ. J. Oper. Res. 15 (2007), 4, 329-349. MR2363903DOI10.1007/s10100-007-0035-x

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.