Optimization of the service start time for an elementary shortest path problem with time windows

We investigate an elementary shortest path problem with resource constraints
where a single capacitated vehicle, initially located at a depot, must serve
a set of customers while respecting their individual time windows. When
the vehicle visits a customer, it delivers the customer's demand and collects
a revenue in return for the delivery. The vehicle can start its trip at any
desired time. The transportation cost is a function of both the total distance
traveled and the duration of the assigned trip. The objective is to determine
the service start time from the depot, the subset of customers to be served,
and the trip to be performed so as to minimize the total loss, which is calculated
as the di erence between the transportation cost and the revenue
collected from the customers. We develop two exact dynamic programming
algorithms which can deal with an in nite number of Pareto-optimal states
arising from the fact that the starting time and the duration of the trip act
like continuous decision variables. We report computational results obtained
with these algorithms and with a faster heuristic for the elementary shortest
path problem. We also examine the performance of these algorithms when
they are used to solve the pricing subproblem arising in the framework of a
column generation algorithm for a related vehicle routing problem with time
windows.