A Selective Many-to-Many Pickup and Delivery Problem With Handling Cost in the Omni-Channel Last-Mile Delivery

被引:2
作者
Li, Yali [1 ]
机构
[1] Huazhong Univ Sci & Technol, Sch Management, Wuhan 430074, Peoples R China
关键词
Costs; Routing; Home appliances; Search problems; Traveling salesman problems; Transportation; Supply and demand; Vehicle routing; Mixed integer linear programming; Heuristic algorithms; Supply chain management; Vehicle routing problem; pickup and delivery; handling cost; mixed integer programming; heuristics; TRAVELING SALESMAN PROBLEM; VEHICLE-ROUTING PROBLEM; SHARING REBALANCING PROBLEM; CUT ALGORITHM; UNPAIRED PICKUP;
D O I
10.1109/ACCESS.2022.3215700
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper introduces a selective many-to-many pickup and delivery problem with handling cost (SMMPDPH) arising in the omni-channel last-mile delivery. In SMMPDPH, each request is associated with multiple pickup and delivery nodes, which provide or require commodities. A request is to load commodities from the pickup nodes and transport them to the delivery nodes. Since the total supply is greater than the total demand, we need to determine the selected subset of pickup nodes to visit for each request. Based on the loading and unloading policy, we take into account the handling cost incurred by additional operations. SMMPDPH aims to obtain a routing plan with the minimum total cost, including the travel cost and handling cost, for a fleet of homogeneous vehicles with limited capacity and driving mileage to satisfy the requests. We present two mixed integer programming formulations of the problem and propose two algorithms, including an iterated local search (ILS) and a memetic algorithm (MA), with specially designed move operators to solve the problem. Experiments on small instances clearly indicate the effectiveness of the two heuristic methods. With a comparison of efficiency on large-scale instances, we find that MA outperforms ILS in terms of both the best and average solution quality.
引用
收藏
页码:111284 / 111296
页数:13
相关论文
共 39 条
  • [11] A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery
    Hernández-Pérez, H
    Salazar-González, JS
    [J]. DISCRETE APPLIED MATHEMATICS, 2004, 145 (01) : 126 - 139
  • [12] The one-commodity pickup-and-delivery traveling salesman problem:: Inequalities and algorithms
    Hernandez-Perez, Hipolito
    Salazar-Gonzalez, Juan-Jose
    [J]. NETWORKS, 2007, 50 (04) : 258 - 272
  • [13] A Branch-and-cut algorithm for the split-demand one-commodity pickup-and-delivery travelling salesman problem
    Hernandez-Perez, Hipolito
    Salazar-Gonzalez, Juan-Jose
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 297 (02) : 467 - 483
  • [14] A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem
    Hernandez-Perez, Hipolito
    Rodriguez-Martin, Inmaculada
    Salazar-Gonzalez, Juan-Jose
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 251 (01) : 44 - 52
  • [15] The Multi-commodity Pickup-and-Delivery Traveling Salesman Problem
    Hernandez-Perez, Hipolito
    Salazar-Gonzalez, Juan-Jose
    [J]. NETWORKS, 2014, 63 (01) : 46 - 59
  • [16] Solving a static repositioning problem in bike-sharing systems using iterated tabu search
    Ho, Sin C.
    Szeto, W. Y.
    [J]. TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2014, 69 : 180 - 198
  • [17] The vehicle routing problem with simultaneous pickup and delivery and handling costs
    Hornstra, Richard P.
    Silva, Allyson
    Roodbergen, Kees Jan
    Coelho, Leandro C.
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2020, 115
  • [18] Integrated sustainable planning of self-pickup and door-to-door delivery service with multi-type stations
    Huang, Zhihong
    Huang, Weilai
    Guo, Fang
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 135 : 412 - 425
  • [19] A Travelling Salesman Problem With Carbon Emission Reduction in the Last Mile Delivery
    Jiang, Li
    Chang, Hongxia
    Zhao, Shuping
    Dong, Junfeng
    Lu, Wenxing
    [J]. IEEE ACCESS, 2019, 7 : 61620 - 61627
  • [20] A review of vehicle routing with simultaneous pickup and delivery
    Koc, Cagri
    Laporte, Gilbert
    Tukenmez, Ilknur
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2020, 122