The Electric Traveling Salesman Problem with Time Windows

R. Roberti; M. Wen

doi:10.1016/j.tre.2016.01.010

The Electric Traveling Salesman Problem with Time Windows

R. Roberti^*
, M. Wen

^*Corresponding author for this work

Department of Applied Mathematics

Technical University of Denmark

Research output: Contribution to journal › Article › peer-review

97 Citations (Scopus)

Abstract

To minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers.

Original language	English
Pages (from-to)	32-52
Number of pages	21
Journal	Transportation Research Part E: Logistics and Transportation Review
Volume	89
DOIs	https://doi.org/10.1016/j.tre.2016.01.010
Publication status	Published - 1 May 2016

Keywords

Dynamic Programming
Electric vehicles
General Variable Neighborhood Search
Green logistics
Time windows
Traveling Salesman

Access to Document

10.1016/j.tre.2016.01.010

Cite this

@article{c218139df82349c1bae37fe97e077db0,

title = "The Electric Traveling Salesman Problem with Time Windows",

abstract = "To minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers.",

keywords = "Dynamic Programming, Electric vehicles, General Variable Neighborhood Search, Green logistics, Time windows, Traveling Salesman",

author = "R. Roberti and M. Wen",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Ltd.",

year = "2016",

month = may,

day = "1",

doi = "10.1016/j.tre.2016.01.010",

language = "English",

volume = "89",

pages = "32--52",

journal = "Transportation Research Part E: Logistics and Transportation Review",

issn = "1366-5545",

}

TY - JOUR

T1 - The Electric Traveling Salesman Problem with Time Windows

AU - Roberti, R.

AU - Wen, M.

PY - 2016/5/1

Y1 - 2016/5/1

N2 - To minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers.

AB - To minimize greenhouse gas emissions, the logistic field has seen an increasing usage of electric vehicles. The resulting distribution planning problems present new computational challenges.We address a problem, called Electric Traveling Salesman Problem with Time Windows. We propose a mixed integer linear formulation that can solve 20-customer instances in short computing times and a Three-Phase Heuristic algorithm based on General Variable Neighborhood Search and Dynamic Programming.Computational results show that the heuristic algorithm can find the optimal solution in most small-size instances within a tenth of a second and achieves goods solutions in instances with up to 200 customers.

KW - Dynamic Programming

KW - Electric vehicles

KW - General Variable Neighborhood Search

KW - Green logistics

KW - Time windows

KW - Traveling Salesman

UR - https://www.scopus.com/pages/publications/84959320602

U2 - 10.1016/j.tre.2016.01.010

DO - 10.1016/j.tre.2016.01.010

M3 - Article

AN - SCOPUS:84959320602

SN - 1366-5545

VL - 89

SP - 32

EP - 52

JO - Transportation Research Part E: Logistics and Transportation Review

JF - Transportation Research Part E: Logistics and Transportation Review

ER -

The Electric Traveling Salesman Problem with Time Windows

Abstract

Keywords

Access to Document

Other files and links

Cite this