车辆路径问题
计算机科学
水准点(测量)
启发式
TRIPS体系结构
数学优化
集合(抽象数据类型)
布线(电子设计自动化)
车队管理
运筹学
算法
工程类
数学
计算机网络
电信
大地测量学
并行计算
程序设计语言
地理
作者
Munise Kübra Şahin,Hande Yaman
出处
期刊:Transportation Science
[Institute for Operations Research and the Management Sciences]
日期:2022-04-19
卷期号:56 (6): 1636-1657
被引量:15
标识
DOI:10.1287/trsc.2022.1146
摘要
The multi-trip vehicle routing problem (MTVRP) extends the well-known VRP by allowing vehicles to perform several trips in a workday. The motivation arises from the new challenges in city logistics that push companies to use smaller and cleaner vehicles such as cargo bikes. With the integration of small vehicles into the fleet, many companies start to operate with a heterogeneous fleet and use multiple depots located in the city centers to reload the small vehicles. Inspired by these new challenges the companies face, we study the heterogeneous fleet multi-depot MTVRP with time windows under shared depot resources where small and large vehicles have different travel times in certain areas. We formulate this problem using workday variables and propose a branch and price algorithm that exhibits an enhanced performance by a new heuristic algorithm based on the reduction in the graph size. The proposed algorithm introduces a new way to compute the completion bounds using the iterative structure of the state-space augmenting algorithm and eliminates the need for solving a separate relaxation. We conduct experiments on modified small- and medium-size instances from Solomon’s benchmark set. The results of our computational experiments show that the proposed algorithm is very effective and can solve instances with up to 40 customers, three depots, and two types of vehicles.
科研通智能强力驱动
Strongly Powered by AbleSci AI