Approximate and exact algorithms for an energy minimization traveling salesman problem
Approximate and exact algorithms for an energy minimization traveling salesman problem
复制标题
能量最小化旅行商问题的近似算法和精确算法
DOI：
10.1016/j.jclepro.2019.119433
复制
发表时间：
2020-03
影响因子：
11.1
通讯作者：
Feng Chu
中科院分区：
文献类型：
--
作者：
Shijin Wang;Ming Liu;Feng Chu
Energy saving is a great challenge for clean transportation.本文研究能量最小化旅行商问题（EMTSP），它是经典旅行商问题（TSP）的一代，也是能量最小化车辆路径问题（EMVRP）的重要理论基础和特例。研究问题的目标是最小化负载（包括车辆的整备质量）和行驶距离的乘积之和。 An approximation algorithm based on the Christofides’s Heuristic is proposed and its worst-case ratio bound is proven. A branch and bound (B&B) algorithm integrated with a fast 1-tree based lower bound is developed to obtain optimal solutions. The results of computational experiments show the efficiency and the effectiveness of the B&B algorithm, as well as the heuristic methods.
Energy saving is a great challenge for clean transportation. In this paper, we study the Energy Minimization Traveling Salesman Problem (EMTSP), which is a generation of the classical Traveling Salesman Problem (TSP), and an important theoretical basis and a special case of the Energy Minimization Vehicle Routing Problem (EMVRP). The objective of the studied problem is to minimize the sum of the product of load (including curb weight of the vehicle) and traveled distances. An approximation algorithm based on the Christofides’s Heuristic is proposed and its worst-case ratio bound is proven. A branch and bound (B&B) algorithm integrated with a fast 1-tree based lower bound is developed to obtain optimal solutions. The results of computational experiments show the efficiency and the effectiveness of the B&B algorithm, as well as the heuristic methods.
登录
查看更多内容
基于燃料和碳排放的异构固定车队车辆路径问题
影响因子：
11.1
作者：
Li Jin;Wang Danping;Zhang Jianghua
通讯作者：
Zhang Jianghua
DOI：
10.1016/j.trd.2017.04.016
发表时间：
2017-07-01
影响因子：
7.6
作者：
Cimen, Mustafa;Soysal, Mehmet
通讯作者：
Soysal, Mehmet
影响因子：
12
作者：
Anurag Tiwari;P. Chang
通讯作者：
Anurag Tiwari;P. Chang
DOI：
10.1007/978-3-642-32147-4_40
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Huber A
通讯作者：
Huber A
DOI：
10.1137/1.9780898718515
发表时间：
2002
期刊：
--
影响因子：
--
作者：
P. Toth;D. Vigo
通讯作者：
P. Toth;D. Vigo