Optimization Online


An Integer Programming approach for the Time-Dependent Traveling Salesman Problem with Time Windows

Agustín Montero(aimontero***at***dc.uba.ar)
Isabel Méndez-Díaz(imendez***at***dc.uba.ar)
Juan José Miranda-Bront(jmiranda***at***dc.uba.ar)

Abstract: Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where the travel times are not assumed to be constant along the day. The motivation to consider the time dependency factor is that it enables to have better approximations to many problems arising from practice. In this paper, we consider the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSP-TW), where the time dependence is captured by considering variable average travel speeds. We propose an Integer Linear Programming model for the problem and develop an exact algorithm, which is compared on benchmark instances with another approach from the related literature. The results show that the approach is able to solve instances with up to 40 customers.

Keywords: Time-Dependent TSP; Time Windows; Integer Linear Programming; Branch and Cut

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 06/29/2016
Entry Accepted: 06/29/2016
Entry Last Modified: 06/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society