An elementary shortest path problem with variable service start time

We consider an elementary shortest path problem with resource constraints (ESPPRC), where a capacitated single vehicle serves a set of delivery and backhaul customers with a revenue and a time window. On a given route, the vehicle can visit a backhaul customer only after all its delivery customers are visited, where a customer is either a delivery or a backhaul customer, but not both. Split deliveries and pick-ups are not allowed. In this problem, multiple trips are allowed so that the vehicle can be assigned to several routes. In addition, the vehicle can begin servicing the customers at any desired time and can be used for at most a fixed amount of time that depends on the shift duration of the assigned driver. Distance and time based variable costs are incurred by serving the customers. In other words, the total cost depends on the total distance traveled and the total amount of time that the vehicle spends by performing the assigned multiple trips. On the other hand, serving a customer yields also a revenue. Therefore, the aim is to determine the optimal service start time of the vehicle from the depot along with the trips to be performed in order to minimize the routing costs minus the collected revenues. Such a problem can be faced as the pricing subproblem in branch-and-price algorithms for vehicle routing problems with additional constraints, where the revenues are equivalent to the dual prizes of the visited vertices.
In general, ESPPRC can be solved to optimality by using a dynamic programming algorithm. However, since the vehicle can start the service at any point in time and is paid based on the total time during which it has been used, our ESPPRC has to take an infinite number of Pareto-optimal states into account. Therefore, we adapt the well-known dynamic programming algorithm according to this feature and develop piecewise linear time functions that represent total traveling and waiting time depending on a variable start time at the depot. Consequently, we propose appropriate dominance rules to discard feasible paths that cannot lead to the optimal solution. Finally, we present computational results.