Dynamic Open Time-Dependent Traveling Salesman Problem With Speed Optimization

Abstract

Increased awareness of people of the problems caused by CO2 emissions brings companies to consider environmental issues in their distribution systems. The rapid advance in technology allows logistics companies to tackle with dynamic nature of distribution networks (e.g., a change in the vehicle speed due to unexpected events). The planned routes at the beginning of the time horizon could be subject to modification at any point in time to account for the recent traffic information. This study addresses a dynamic open time-dependent traveling salesman problem. The problem also involves speed optimization that aims to find optimal vehicle speed in a dynamic setting by respecting real-time traffic conditions. We develop a mixed integer linear programming (MILP) formulation for the addressed problem to determine routing and vehicle speed decisions. Furthermore, a MILP-based myopic-clustering decomposition heuristic algorithm has been introduced to solve large-sized instances within reasonable solution times. The use of the heuristic algorithm provides decision-makers with a responsiveness capacity by enabling fast incorporation of dynamically observed data during operations. The numerical analyses demonstrate the potential benefits of employing the proposed tools.