M. Roca-Riu, E. Fernández, G. Speranza
Most major cities present a dense and complex urban fabric, which difficult considerably last-mile deliveries. Different transport carriers offer transport services located all over the city, which in the end entails a multiple number of trips from the different companies to the same areas to perform their deliveries. From a system point of view, this operation might easily be not efficient. Performing several trips in the same area means more vehicle kilometers. And in turn, that generates negative effects to all stakeholders involved in last mile deliveries. It is more costly from the whole set of transport companies. And at the same time, it generates more pollution, traffic and space occupancy in the city, which is a nuisance for citizens. In particular, we might find different situations where even the same customer is visited for more than one carrier in the same time horizon. We will call them shared customers. In this cases, the expected potential saving with the collaboration between these carriers is assumed to be more attractive since carriers do not need to modify their routes to accommodate demand from other carriers. Carriers can agree to collaborate by interchanging the loads between the depots before the beginning of the tours, and then not all carriers with demand for the given customer have to visit it.
The customers in urban areas are usually very concentrated. There are many customers located in a reduced area, specially in commercial neighborhoods. For that reason, even in situations where there are no strictly shared costumers from different carriers we can use an aggregation of different customers. We can build a macro-customer, which is an aggregation of some customers that are located very close among them, in the same street section or in the same block. Where in terms of routing we can consider that the visiting of this macro customer can easily give service to all the customers. We could also consider to use the term Nearby Customer, defined as a set of customers with a given maximum distance among them. Furthermore, in regular but non-urgent deliveries, the time horizon can be considered to be more than one day, or even a week. Then, it’s more common to have shared customers (or nearby customers) receiving goods from different carriers, which could be sent the same route by a unique carrier.
We assume that a set of carriers are operating in the same area, and are willing to collaborate to save distribution costs. From the whole group of customers in the region, we have customers that only receive goods from one carrier, but we have customers that receive goods from more than one carrier of the area. We consider that common customers can be served by one of their carriers, and carriers might need to transfer beforehand the goods between the depots. The objective of the problem is minimizing the total distribution costs given the fact that exclusive customers can not be transferred, but shared customers can be exchanged and served by one of the other companies.
The work presents two formulations for the problem, one vehicle based-formulation and the other flow based-formulation. Both formulations are compared. A set of test problems is generated based on instances proposed for the Multiple Depot Vehicle Routing problem of Cordeau et al. (1997), reduced to size of 30 customers.
Keywords: Vehicle Routing Problem, Collaboration
Scheduled
F1 Routing 1
October 2, 2015 9:00 AM
Salón de actos
