Skip to Main content Skip to Navigation
Journal articles

Approximate and exact algorithms for an energy minimization traveling salesman problem

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02427206
Contributor : Frédéric Davesne <>
Submitted on : Friday, January 3, 2020 - 12:51:40 PM
Last modification on : Monday, July 6, 2020 - 10:38:36 AM

Identifiers

Citation

Shijin Wang, Ming Liu, Feng Chu. Approximate and exact algorithms for an energy minimization traveling salesman problem. Journal of Cleaner Production, Elsevier, 2020, 249, pp.119433. ⟨10.1016/j.jclepro.2019.119433⟩. ⟨hal-02427206⟩

Share

Metrics

Record views

78