An integer programming approach for the time-dependent traveling salesman problem with time windows |
| |
| Affiliation: | 1. Departamento de Computación, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, C1428EGA, CABA, Argentina;2. Universidad Torcuato Di Tella, Av. Figueroa Alcorta 7350, C1428BCW, CABA, Argentina;3. Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina;4. CONICET-Universidad de Buenos Aires. Instituto de Investigación en Ciencias de la Computación (ICC). Buenos Aires, Argentina;1. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg 620219, Russia;2. Ural Federal University, pr. Lenina 51, Yekaterinburg 620083, Russia;1. Department of Industrial Engineering, Tsinghua University, Beijing, 100084, China;2. School of Industrial Engineering, Eindhoven University of Technology, Eindhoven, Netherlands |
| |
| 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
