Joint route planning with customer priorities
Problem context and motivation
We consider a less-than-truckload, last-mile delivery problem for a group of collaborating companies that operate in the same geographical region. Due to what is called “geographical overlap” in the distribution area, the total number of kilometres driven can be reduced if shipments of different suppliers are redistributed over the available vehicles such that each vehicle serves a part of the area.
Consider, for example different parcel delivery companies that cover the same region or joint deliveries within a city organized by different suppliers. Working from home, you easily notice that multiple carriers drive through your street during a single day to deliver packages to you and/or your neighbours. If all these parcels that need to be delivered to addressess in your street would be relocated to a single van, it is sufficient that only one vehicle visits your neighbourhood to provide the delivery service.
We extended the problem with a feature that accounts for individual customer urgency. Given limitations to what can be done during a single planning period (e.g., a day), it is likely that some deliveries have to be postponed to the next period. At the same time, some customers will likely have more priority to not delay the service. You might, e.g., prioritize customers that are waiting the longest or those that paid a surplus to receive a fast service.
By means of a set of computational experiments, we study the relationship between the following problem-specific elements: the individual partner’s strategy when setting the customer priorities, the route planning and the allocation of operational costs among the collaborating partners.
Compensation for non-delivery
Each company is free to decide on the importance for each of its customers to be included in the vehicle trips. This is done by defining a monetary “compensation for non-delivery”, i.e., a penalty fee that should be paid if the service to this customer is postponed. If this penalty fee is smaller than the cost of providing the service, the customer service will be postponed anyway, as this is cheaper than providing the service. A larger penalty cost increases the urgency of the customer, as postponing the service becomes more expensive than providing the service. The larger the penalty, the more you are willing to include the customer in the schedule for the current period (eventually by making additional detours) to avoid these compensation payments. This explains the dependency between a partner’s strategy and the operational planning.
Allocation of operational costs
At the end of the day, the operational costs of the executed vehicle trips should be covered by the collaborating companies. The cost that has to be paid by each company depends on two aspects: the operational planning and the partner’s strategy.
First, the portion of the operational cost that should be paid by each company depends on the customers included in the solution. The more customers included, the more the corresponding company should contribute. This contribution should also be based on the marginal cost of including this customer in the tour: a customer that is located close to other visited customers is ‘cheaper’ than customers that are isolated and for which larger detours were necessary. Also recall that the higher the compensation for non-delivery set by the companies for its customers, the higher the likelihood that more of its customers are included in the tour.
Second, the allocated cost should also depend directly on the compensation costs set by the company. Companies should be discouraged from setting too large compensation for non-delivery values. By artificially increasing these penalty costs, the group is forced to prioritize the customers from this particular company, even if this is very costly. As a result, the limited vehicle capacity is used for making detours for this single partner, leading to inefficient use of the resources from the coalition. To alleviate this problem, a company should be ‘punished’ via the cost allocation method if it sets unreasonable high compensation penalties compared to its coalition partners.
Feedback to improve the performance of the coalition over time
As discussed above, there is a direct (as well as an indirect) relationship between the behaviour/strategy of an individual company and the cost that it should pay. Conclusively, the presented framework can be used to steer the individual company strategies. It provide the necessary incentives to all partners to behave according to what is best for the coalition as a whole. At the same time, it makes sure that if a company deviates from what is best for the group – which might be desirable for a company in certain situations – this company bears the monetary consequences of this individualistic action.