A dynamic programming approach to multi-objective time-dependent capacitated single vehicle routing problems with time windows

A single vehicle performs several tours to serve a set of geographically dis- persed customers. The vehicle has a finite capacity and is only available for a limited amount of time. Moreover, tours' duration is restricted (e.g. due to quality or security issues). Because of road congestion, travel times are time-dependent: depending on the departure time at a customer, a different travel time is incurred. Furthermore, all customers need to get delivered in their specicified time windows. Contrary to most of the literature, we con- sider a multi-objective cost function: simultaneously minimizing the total time traveled including waiting times at customers due to time windows, and maximizing the total demand fulfilled. Efficient dynamic programming algorithms are developed to compute the Pareto set of routes, assuming a specific structure for time windows and travel time profiles.