Request acceptance with overbooking in dynamic and collaborative vehicle routing

Yannick Oskar Scherr, Margaretha Gansterer and Richard F. Hartl

European Journal of Operational Research, 2024, vol. 314, issue 2, 612-629

Abstract: 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.

Keywords: Routing; Dynamic request acceptance; Multi-vehicle pickup and delivery problem; Horizontal collaboration; Combinatorial auction (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723007713
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:314:y:2024:i:2:p:612-629

DOI: 10.1016/j.ejor.2023.10.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().