A covering traveling salesman problem with profit in the last mile delivery

被引：0
作者：
Li Jiang
Xiaoning Zang
Junfeng Dong
Changyong Liang
机构：
[1] Hefei University of Technology,School of Management
[2] Ministry of Education,Key Laboratory of Process Optimization and Intelligent Decision
来源：
Optimization Letters | 2022年 / 16卷
关键词：
Covering traveling salesman problem; Profit; Variable neighborhood search; Last mile delivery;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper introduces and formulates a covering traveling salesman problem with profit arose in the last mile delivery. In this problem, a set of vertices including a central depot, customers and parcel lockers (PL) are given, and the goal is to construct a Hamiltonian cycle within a pre-defined cost over a subset of customers and/or PLs to collect maximum profits, each unvisited customer is covered by a PL in the cycle or outsourced. To solve the problem, a two-phase heuristic combined with a feasible solution construction procedure and an improvement procedure is proposed. The algorithm is evaluated on two sets of instances, and the computational results indicated its efficiency.
引用
收藏
页码：375 / 393
页数：18
相关论文
共 90 条
  • [1] Zhou L(2018)A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution Eur. J. Oper. Res. 265 765-778
  • [2] Baldacci R(1999)Heuristics for the traveling salesman problem with pickup and delivery Comput. Oper. Res. 26 699-714
  • [3] Vigo D(2015)On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances Optimization Letters 9 1247-1254
  • [4] Wang X(2018)Solving the family traveling salesman problem Eur. J. Oper. Res. 267 453-466
  • [5] Gendreau M(1989)The Covering Salesman Problem Transportation Science 23 208-213
  • [6] Laporte G(1997)The Covering Tour Problem Oper. Res. 45 568-576
  • [7] Vigo D(2000)Heuristics for the multi-vehicle covering tour problem Computers Operations Research 27 29-42
  • [8] Hoos HH(2016)Time constrained maximal covering salesman problem with weighted demands and partial coverage Comput. Oper. Res. 76 226-237
  • [9] Stützle T(2012)An integer programming-based local search for the covering salesman problem Comput. Oper. Res. 39 2594-2602
  • [10] Bernardino R(2015)Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem Computers Industrial Engineering 83 244-251
123456789