旅行商问题
线性规划
机器人
集合(抽象数据类型)
启发式
遗传算法
计算机科学
整数规划
数学优化
拉格朗日松弛
贪婪算法
运筹学
递归(计算机科学)
工程类
人工智能
数学
机器学习
算法
程序设计语言
作者
Yanlu Zhao,Diego Cattaruzza,Ningxuan Kang,Roberto Roberti
出处
期刊:Transportation Science
[Institute for Operations Research and the Management Sciences]
日期:2024-01-01
卷期号:58 (1): 219-239
被引量:1
标识
DOI:10.1287/trsc.2023.0169
摘要
Online e-commerce giants are continuously investigating innovative ways to improve their practices in last-mile deliveries. Inspired by the current practices at JD.com (the largest online retailer by revenue in China), we investigate a delivery problem that we call the traveling salesman problem with bike and robot (TSPBR), where a cargo bike is aided by a self-driving robot to deliver parcels to customers in urban areas. We present two mixed-integer linear programming models and describe a set of valid inequalities to strengthen their linear relaxation. We show that these models can yield optimal solutions of TSPBR instances with up to 60 nodes. To efficiently find heuristic solutions, we also present a genetic algorithm based on a dynamic programming recursion that efficiently explores large neighborhoods. We computationally assess this genetic algorithm on instances provided by JD.com and show that high-quality solutions can be found in a few minutes of computing time. Finally, we provide some managerial insights to assess the impact of deploying the bike-and-robot tandem to deliver parcels in the TSPBR setting.
科研通智能强力驱动
Strongly Powered by AbleSci AI