Exact approaches for the pickup and delivery problem with loading cost

被引:13
作者
Xue, Li [1 ,2 ,3 ]
Luo, Zhixing [1 ]
Lim, Andrew [1 ,2 ,3 ]
机构
[1] Nanjing Univ, Sch Management & Engn, Int Ctr Management Sci & Engn, Nanjing 210093, Jiangsu, Peoples R China
[2] Xi An Jiao Tong Univ, Sch Management, Xian 710049, Shaanxi, Peoples R China
[3] City Univ Hong Kong, Dept Management Sci, Kowloon Tong, Hong Kong, Peoples R China
来源
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE | 2016年 / 59卷
关键词
Pickup and delivery problem; Loading cost; Branch-and-price; Branch-and-cut; Healthcare transportation; A-RIDE PROBLEM; VEHICLE-ROUTING PROBLEM; SHORTEST-PATH PROBLEM; NEIGHBORHOOD SEARCH; CUT ALGORITHM; BRANCH; PRICE; TRANSPORTATION; MODELS;
D O I
10.1016/j.omega.2015.05.012
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (POP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame. (c) 2015 Elsevier Ltd. All rights reserved.
引用
收藏
页码:131 / 145
页数:15
相关论文
共 44 条
  • [1] THE PRECEDENCE-CONSTRAINED ASYMMETRIC TRAVELING SALESMAN POLYTOPE
    BALAS, E
    FISCHETTI, M
    PULLEYBLANK, WR
    [J]. MATHEMATICAL PROGRAMMING, 1995, 68 (03) : 241 - 265
  • [2] 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
  • [3] Dynamic pickup and delivery problems
    Berbeglia, Gerardo
    Cordeau, Jean-Francois
    Laporte, Gilbert
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (01) : 8 - 15
  • [4] The dial-a-ride problem: models and algorithms
    Cordeau, Jean-Francois
    Laporte, Gilbert
    [J]. ANNALS OF OPERATIONS RESEARCH, 2007, 153 (01) : 29 - 46
  • [5] A branch-and-cut algorithm for the dial-a-ride problem
    Cordeau, Jean-Francois
    [J]. OPERATIONS RESEARCH, 2006, 54 (03) : 573 - 586
  • [6] The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms
    Cordeau, Jean-Francois
    Laporte, Gilbert
    [J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (02): : 89 - 101
  • [7] 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
  • [8] DECOMPOSITION PRINCIPLE FOR LINEAR-PROGRAMS
    DANTZIG, GB
    WOLFE, P
    [J]. OPERATIONS RESEARCH, 1960, 8 (01) : 101 - 111
  • [9] The bike sharing rebalancing problem: Mathematical formulations and benchmark instances
    Dell'Amico, Mauro
    Hadjicostantinou, Eleni
    Iori, Manuel
    Novellani, Stefano
    [J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2014, 45 : 7 - 19
  • [10] Desaulniers G., 1998, A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems