Request acceptance with overbooking in dynamic and collaborative vehicle routing

We consider the problem setting of a less-than-truckload carrier serving stochastic customer requests. Each request must be answered dynamically by accepting or rejecting it immediately. On the next day, accepted requests are served in routes using a set of vehicles with limited load capacity and route duration. After the request acceptance phase and before the fulfillment, multiple carriers participate in a combinatorial auction to exchange requests. An auctioneer allocates the bundles of requests to carriers according to their bids in a cost-minimizing way and distributes the auction profits. This type of horizontal collaboration provides cost savings and contributes to reducing negative impacts of transportation. We describe the carrier’s optimization problem of maximizing profit as a Markov decision process that comprises the sequential decisions in all phases, i.e., request acceptance, request selection for the auction, bidding, and routing. For solving a version of the vehicle routing problem with pickups and deliveries, heuristic approaches are proposed that achieve efficient and balanced routes. We design overbooking policies for strategically accepting more requests bearing in mind the options provided by the auction. Computational results show that – by trading requests in an auction – carriers can accept more requests than they could serve on their own. The carriers’ request acceptance decisions impact their individual profits and the overall collaboration savings. The largest benefits can be achieved with an overbooking policy that prescribes which requests should be accepted by all carriers, based on the locations of both the request and the carriers’ depots.