New mixed integer-programming model for the pickup-and-delivery problem with transshipment

被引:76
作者
Rais, A. [1 ]
Alvelos, F. [1 ]
Carvalho, M. S. [1 ]
机构
[1] Univ Minho, Dept Prod & Sistemas, Ctr Algoritmi, P-4710057 Braga, Portugal
关键词
Integer programming; Pickup-and-delivery; Vehicle routing; Transshipment; Transportation-on-demand; Modeling; SEARCH;
D O I
10.1016/j.ejor.2013.10.038
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In recent years, many important real-world applications are studied as "rich" vehicle routing problems that are variants and generalizations of the well-known vehicle routing problem. In this paper we address the pickup-and-delivery version of this problem and consider further generalization by allowing transshipment in the network. Moreover, we allow heterogenous vehicles and flexible fleet size. We describe mixed integer-programming formulations for the problem with and without time windows for services. The number of constraints and variables in the models are bounded by polynomial size of the problem. We discuss several problem variants that are either captured by our models or can be easily captured through simple modifications. Computational work gave promising results and confirms that transshipment in network can indeed enhance optimization. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码:530 / 539
页数:10
相关论文
共 37 条
  • [1] [Anonymous], 2002, The vehicle routing problem pp
  • [2] [Anonymous], 2008, J BETRIEBSWIRTSCHAFT, DOI DOI 10.1007/S11301-008-0036-4
  • [3] [Anonymous], 2011, ROADMAP SINGLE EUROP
  • [4] Assad A.A., 1988, VEHICLE ROUTING METH, P7
  • [5] Static pickup and delivery problems: a classification scheme and survey
    Berbeglia, Gerardo
    Cordeau, Jean-Francois
    Gribkovskaia, Irina
    Laporte, Gilbert
    [J]. TOP, 2007, 15 (01) : 1 - 31
  • [6] Bouros Panagiotis, 2011, Advances in Spatial and Temporal Databases. Proceedings 12th International Symposium (SSTD 2011), P112, DOI 10.1007/978-3-642-22922-0_8
  • [7] Christiansen M, 2007, HBK OPERAT RES MANAG, V14, P189, DOI 10.1016/S0927-0507(06)14004-9
  • [8] Cordeau J. F., 2002, SIAM MONOGRAPHS DISC, V9, P175
  • [9] The dial-a-ride problem: models and algorithms
    Cordeau, Jean-Francois
    Laporte, Gilbert
    [J]. ANNALS OF OPERATIONS RESEARCH, 2007, 153 (01) : 29 - 46
  • [10] The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method
    Cortes, Cristian E.
    Matamala, Martin
    Contardo, Claudio
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (03) : 711 - 724