The multi-vehicle profitable pick up and delivery routing problem with uncertain travel times

This paper addresses a variant of the known selective pickup and delivery problem with time windows. In this problem, a fleet composed of several vehicles with a given capacity should satisfy a set of customers requests consisting in transporting goods from a supplier (pickup location) to a customer (delivery location). The selective aspect consists in choosing the customers to be served on the basis of the profit collected for the service. Motivated by urban settings, wherein road congestion is an important issue, in this paper, we address the profitable pickup and delivery problem with time windows with uncertain travel times. The problem under this assumption, becomes much more involved. The goal is to find the solution that maximizes the net profit, expressed as the difference between the collected revenue, the route cost and the cost associated to the violation the time windows. This study introduces the problem and develops a solution approach to solve it. Very preliminary tests are performed in order to show the efficiency of developed method to cope with the problem at hand.