Vehicle Routing Problem with Time Windows: A Deterministic Annealing approach

Mayank Baranwal, Pratik M. Parekh, Lavanya Marla, Srinivasa M. Salapaka, Carolyn L. Beck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Vehicle Routing Problem with Time-Windows (VRPTW) is an important problem in allocating resources on networks in time and space. We present in this paper a Deterministic Annealing (DA)-based approach to solving the VRPTW with its aspects of routing and scheduling, as well as to model additional constraints of heterogeneous vehicles and shipments. This is the first time, to our knowledge, that a DA approach has been used for problems in the class of the VRPTW. We describe how the DA approach can be adapted to generate an effective heuristic approach to the VRPTW. Our DA approach is also designed to not get trapped in local minima, and demonstrates less sensitivity to initial solutions. The algorithm trades off routing and scheduling in an n-dimensional space using a tunable parameter that allows us to generate qualitatively good solutions. These solutions differ in the degree of intersection of the routes, making the case for transfer points where shipments can be exchanged. Simulation results on randomly generated instances show that the constraints are respected and demonstrate near optimal results (when verifiable) in terms of schedules and tour length of individual tours in each solution.

Original languageEnglish (US)
Title of host publication2016 American Control Conference, ACC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages790-795
Number of pages6
ISBN (Electronic)9781467386821
DOIs
StatePublished - Jul 28 2016
Event2016 American Control Conference, ACC 2016 - Boston, United States
Duration: Jul 6 2016Jul 8 2016

Publication series

NameProceedings of the American Control Conference
Volume2016-July
ISSN (Print)0743-1619

Other

Other2016 American Control Conference, ACC 2016
CountryUnited States
CityBoston
Period7/6/167/8/16

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Vehicle Routing Problem with Time Windows: A Deterministic Annealing approach'. Together they form a unique fingerprint.

Cite this