European Journal of Operational Research 314 (2024) 612–629

Contents lists available at ScienceDirect

European Journal of Operational Research

journal homepage: [Link]/locate/eor

Production, manufacturing, transportation and logistics

Request acceptance with overbooking in dynamic and collaborative vehicle

routing
Yannick Oskar Scherr a,b ,∗, Margaretha Gansterer a , Richard F. Hartl b
a Department of Operations, Energy, and Environmental Management, University of Klagenfurt, Universitätsstraße 65–67, 9020, Klagenfurt, Austria
b
Department of Business Decisions and Analytics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090, Vienna, Austria

ARTICLE INFO ABSTRACT

Keywords: We consider the problem setting of a less-than-truckload carrier serving stochastic customer requests. Each
Routing request must be answered dynamically by accepting or rejecting it immediately. On the next day, accepted
Dynamic request acceptance requests are served in routes using a set of vehicles with limited load capacity and route duration. After the
Multi-vehicle pickup and delivery problem
request acceptance phase and before the fulfillment, multiple carriers participate in a combinatorial auction
Horizontal collaboration
to exchange requests. An auctioneer allocates the bundles of requests to carriers according to their bids in a
Combinatorial auction
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.

1. Introduction chains to comply with sustainability-related goals (Guo et al., 2022).

With increased communication and data exchange capabilities, sharing
In times of e-commerce and competitive markets, fast response information between service providers can nowadays be realized via
times by service providers are crucial to satisfy customers and to digital platforms where transaction costs are negligible. For transporta-
prevent them from choosing competitors (Speranza, 2018). At the tion applications, different forms of collaboration have emerged in
same time, service providers aim to utilize their resources in the most literature and practice, that require the consideration of both opera-
efficient way. In delivery applications, those two goals are typically tions research techniques and game-theoretic aspects (Cleophas et al.,
contradictory as commitments by carriers to fulfill delivery requests 2019).
under uncertainty can lead to inefficient utilization of resources. More Horizontal collaboration, which describes multiple companies op-
specifically, the marginal costs for serving an individual request only erating at the same level of the supply chain actively cooperating,
become known after all requests that are fulfilled with the same re- represents a promising and particularly challenging approach (Crui-
sources are known. These efficiency losses not only impact the indi- jssen et al., 2007; Ferrell et al., 2019; Pan et al., 2019). A prominent
vidual service provider’s profit margins but also affect society and the application is the exchange of requests between carriers to achieve ef-
environment as a whole, e.g., in terms of avoidable traffic volume and ficiency gains in their fulfillment, e.g., when serving requests in routes.
To enable horizontal collaboration in a decentralized way without
emissions (Agatz et al., 2020).
requiring carriers to reveal sensitive information, research has turned to
Collaboration between companies is widely seen as a measure to uti-
combinatorial auctions as an efficient exchange mechanism (Gansterer
lize resources more efficiently, especially with the rise of the so-called
& Hartl, 2018b).
sharing economy (Gansterer et al., 2022) and the urgency of supply

∗ Corresponding author at: Department of Operations, Energy, and Environmental Management, University of Klagenfurt, Universitätsstraße 65–67, 9020,
Klagenfurt, Austria.
E-mail address: [Link]@[Link] (Y.O. Scherr).

[Link]
Received 4 January 2023; Accepted 9 October 2023
Available online 11 October 2023
0377-2217/© 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ([Link]
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 1. Overview of the interactions on the primary and the secondary market.

In this paper, we focus on the operational problem setting of a less- Hartl, 2018b) to this date focuses on static and deterministic problem
than-truckload carrier in an urban environment that fulfills customer settings concerned exclusively with the secondary market. Studies on
requests to transport goods from pickup to delivery locations. Incoming dynamic settings typically neglect the perspective of the individual car-
requests must be answered immediately but are served in vehicle routes rier and its overall optimization problem that likely includes decisions
in a later time period. After requests are accepted and before they must on the primary market. On the other hand, there is a body of literature
be served, the carrier is able to exchange requests with other carriers in on pickup and delivery problems (Parragh et al., 2008) and their
a combinatorial auction, organized by a third-party auctioneer. Thus, dynamic versions (Berbeglia et al., 2010). Moreover, a multitude of
each carrier faces a primary market, concerning the interaction with
approaches have been developed to model and solve stochastic dynamic
customers, and a secondary market, concerning the interaction with
vehicle routing problems without recognizing horizontal collaboration.
other carriers.
In the primary market phase, stochastic customer requests, featuring With this paper, we provide the following contributions for studying
a pickup location, a delivery location, a volume, and a revenue, arrive a pickup and delivery problem with dynamic request acceptance and
over the course of a finite time horizon. The carrier must answer each auction-based collaboration.
request dynamically by either accepting or rejecting it immediately.
• We model the carrier’s sequential optimization problem as a
The primary market phase ends at a cutoff time, e.g., the end of the
Markov decision process (MDP) that depicts the primary and the
day, prescribed by the time the auction takes place. After all requests
secondary market phases in an integrated way.
are known, e.g., on the next day, the requests must be served in routes
using a fleet of vehicles with limited load capacity and route duration. If • We propose heuristic approaches for generating preliminary route
a request cannot be served or traded in the auction, costly penalty fees plans for multiple vehicles when making request acceptance,
apply, e.g., for late cancellation or commissioning of a courier service. request selection, and bidding decisions. The approaches combine
The secondary market phase describes the time period during which cheapest insertion with different route-assignment policies, of
the auction is prepared, conducted, and evaluated. Multiple carriers which the policy that maintains balanced routes performs best.
participate in this auction, each being seller and buyer, to trade requests • We propose heuristic policies for considering the options provided
among each other. The exchange is organized by an independent auc- by the auction (secondary market) already when making revenue-
tioneer in the form of a combinatorial auction. Each carrier selects a set generating request acceptance decisions (primary market). We
of requests to submit to the auction pool, based on which the auctioneer specifically develop different ‘‘overbooking’’ policies for accept-
generates bundles of requests. After all carriers have placed bids on ing more requests than can be served before the auction takes
each bundle denoting their price for serving the included requests, place. The best-performing policy considers the distance between
the auctioneer allocates bundles to carriers such that the total cost requests’ pickup and delivery locations as well as the carriers’
is minimized and distributes the auction profits. At the end of the depot locations.
planning horizon, the carrier commits to fulfilling untraded accepted • We conduct numerical experiments to provide insights into the
requests and auction-acquired requests. In Fig. 1, the interactions of
interrelation of the primary and the secondary market and to
customers, carriers, and the auctioneer on the primary market and the
study the value for carriers to consider them in an integrated way.
secondary market are schematically illustrated.
The results show that, in this problem setting, it is important to
Focusing on the problem setting of each individual carrier, their
recognize the revenue-generating request acceptance to achieve
objective is to maximize profit. Revenues are generated by accepting
customer requests, while the fulfillment of requests incurs costs that higher collaboration savings. Focusing on the effects of overbook-
can be reduced via the auction. In total, the carrier’s decisions consist of ing, we find that, in asymmetric settings with only one carrier
request acceptance, request selection, bidding, and vehicle routing. Not using an overbooking policy, this carrier is negatively impacted
only are all of those decisions interrelated but, moreover, the customer compared to symmetric settings, in which all carriers use the same
requests, the other carriers’ request selection and bids, and, finally, the successful overbooking policy.
auctioneer’s bundle allocation are stochastic. The request acceptance
The article is structured in the following way. In Section 2, we
decisions in particular have considerate effects on all subsequent deci-
sions. The number and types of requests that are accepted impact the review related literature before describing the overall problem setting
evaluation of requests in the request selection decision, the evaluation in Section 3. We formally define the auction-based exchange mech-
of bundles in the bidding decision, and finally the fulfillment costs anism in Section 4 and present the sequential optimization problem
when solving the routing problem ahead of the implementation. of each carrier participating in the auction in Section 5. The solution
Turning our attention to the existing literature, we note that re- approaches are described in Section 6 before we present the numerical
search on horizontal collaboration in transportation (Cleophas et al., experiments in Section 7. Finally, we conclude and provide perspectives
2019) and, particularly, on collaborative vehicle routing (Gansterer & for future research in Section 8.

613
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

2. Related literature them. Gansterer, Hartl and Sörensen (2020) show that approximate
bidding strategies incur no significant loss in solution quality for single-
Related literature to this work can be located in the fields of collab- vehicle routing problems but more sophisticated strategies are required
orative vehicle routing, that incorporates principles from mechanism in the multi-vehicle case. For assigning bundles to carriers according to
design and auction theory, and stochastic dynamic vehicle routing, their bids, the so-called winner determination problem is solved (e.g.,
particularly with pickup and delivery requests. Pekeč & Rothkopf, 2003). Although it is an NP-hard problem, solving
even large instances is fairly easy in practice. The last auction phase
2.1. Collaborative vehicle routing comprises the determination of payments to individual carriers that
are influenced by some profit sharing mechanism. For a comprehensive
Collaborative vehicle routing is a form of horizontal collaboration review on such mechanisms in collaborative transportation, we refer to
in which groups of carriers collaborate by exchanging transportation the review by Guajardo and Rönnqvist (2016).
requests among each other. The survey by Gansterer and Hartl (2018b) The majority of collaborative vehicle routing studies consider a
divides the literature into three major streams: centralized collaborative static and deterministic routing problem that is solved once by each
planning, decentralized planning without auctions, and auction-based carrier before entering the auction. A dynamic collaborative routing
decentralized planning. Since the carriers in our problem setting would problem is approached by Wang and Kopfer (2015) using a rolling hori-
likely not be willing to give permission to a central authority to manage zon planning approach, but the problem is restricted to full-truckload
customer acceptance and fulfillment decisions for them, we consider requests only. Los et al. (2020) study a dynamic collaborative routing
decentralized planning. Literature further suggests that auctions – al- problem combining multi-agent systems and combinatorial auctions,
though they involve a certain complexity – can exploit the collaboration particularly focusing on the value of information sharing among carri-
potential of decentralized planning in a suitable way, as they allow ers. In Los et al. (2022), large-scale instances with up to 1000 carriers
to implicitly share information on collaborators’ preferences without are approached. Requests are iteratively offered in multiple auction
revealing sensitive information (Gansterer et al., 2018). rounds and reallocated between carriers according to their bids. How-
For collaborative vehicle routing problems, combinatorial auctions ever, the interaction between carriers and customers on the primary
are typically considered in which bundles are traded as combinations market is not considered in those works.
of individual requests (de Vries & Vohra, 2003; Pekeč & Rothkopf, Most of the research on collaborative routing considers pickup and
2003). This concurs with the combinatorial nature of the routing delivery problems as the fulfillment problem that is faced by each
problem as a request may only be attractive in combination with carrier. For more detailed classifications and reviews on pickup and
others. Combinatorial auctions further ensure that a bundle can al- delivery problems in general, we refer to Battarra et al. (2014), Parragh
ways be feasibly served by the carrier to which it is assigned. The et al. (2008), Savelsbergh and Sol (1995). In this work, we focus on a
survey by Abrache et al. (2007) discusses further issues arising in pickup and delivery problem that additionally considers outsourcing of
the design of such combinatorial auctions. Focusing on collaborative requests in exchange for paying a penalty fee. Similar problem formu-
vehicle routing, Krajewska and Kopfer (2006) first present a design of lations are faced in other streams of literature without any connection
an auction-based exchange mechanism for collaborating carriers that to collaboration, e.g., in vehicle routing problems considering a private
each face a pickup and delivery problem with time windows (PDPTW). fleet and outside carriers (Archetti et al., 2014; Chu, 2005).
A structured framework for combinatorial auctions in transportation
applications is provided by Berger and Bierwirth (2010). Its five phases 2.2. Stochastic dynamic vehicle routing
comprise request selection, bundling, bidding, winner determination,
and profit sharing. Subsequent works have approached all of those Another stream of literature – mostly independent from collabora-
auction phases. In the following, we provide a brief overview on tive routing – is concerned with stochastic dynamic vehicle routing
selected contributions, structured by the phases, but refer to the survey problems. In such problems, dynamic decisions, such as accepting
by Gansterer and Hartl (2018b) for a more comprehensive analysis. customer requests and adapting route plans, must be made under
In the first phase, carriers select the requests they want to trade. uncertainty, e.g., with regard to demand or resource availability. The
Gansterer and Hartl (2016) propose taking geographical aspects into dynamic request acceptance decisions in our problem are similar to
account as a criterion for request selection. Schopka and Kopfer (2017) those considered by Ehmke and Campbell (2014) for attended home
consider so-called pre-selection strategies that recognize the approxi- delivery with time windows and by Klapp et al. (2020) for a dynamic
mate potential of a request to increase the carrier’s profit whereas Li dispatch waves problem in a same-day delivery system. Collaboration
et al. (2016) propose to solve a PDPTW with reserved requests. Re- or overbooking has not been considered in these works. For a more
garding the bundling phase, Gansterer and Hartl (2018a) show that comprehensive overview of stochastic dynamic vehicle routing litera-
the set of bundles the auctioneer generates can be efficiently reduced ture, we refer to the surveys by Pillac et al. (2013), Rios et al. (2021),
by identifying a subset of attractive bundles using a genetic algorithm. Ritzinger et al. (2016), Soeffker et al. (2022). A more focused review on
A scenario-based bundling approach is proposed by Rüther and Rieck dynamic pickup and delivery problems is provided by Berbeglia et al.
(2022) for a PDPTW with heterogeneous fleets. In Gansterer, Hartl (2010).
and Sörensen (2020), it is further shown that auctioneer-built bundles In most of the recent contributions, the arising sequential opti-
provide higher collaboration gains than if carriers compose bundles by mization problem is modeled as an MDP. A more problem-specific
themselves. Gansterer, Hartl and Savelsbergh (2020) show that carriers formulation is provided by Ulmer et al. (2020) with the route-based
can enhance the collaboration gains by sharing additional information MDP, in which preliminary route plans are explicitly depicted in the
on an aggregate level in the request selection and bundling phase. In all state description. Although we are not aware of any study regarding a
of those works, requests are traded also based on their revenue, i.e., the stochastic dynamic vehicle routing problem in a collaborative environ-
cost paid by the customer. In our problem setting, however, requests ment, some approaches for modeling sequential decision making are
are traded purely on a cost basis as revenues are strictly determined transferable to our work.
on the primary market, thus some of the proposed approaches may not While large state, decision, and transition spaces (known as the
provide comparable results. ‘‘curses of dimensionality’’) typically prohibit the optimal solution of an
In the bidding phase, carriers place their bids on the offered bun- MDP in such applications (Powell, 2011), mostly heuristic approaches
dles. The bid values are usually determined by solving the respective are applied to find good solutions. Some of these solution approaches
routing problem and comparing the solution value of an instance are able to recognize the uncertainty of later states of the process when
including the requests of a bundle with the solution value without making decisions, either through sampling of future scenarios (Ausseil

614
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 2. Timeline of decisions in the problem setting of a carrier.

et al., 2022) or by approximating values of post-decision states (van accepted requests. The carrier uses a fleet of vehicles to serve the pickup
Heeswijk et al., 2019). Such sophisticated solution approaches, classi- and delivery requests within routes that are executed after all requests
fied as Categories IIa and IIb in the survey by Soeffker et al. (2022), are known, e.g., on the next day. The duration of each route and the
however, are mainly applied to solve problem settings with only one load capacity of each vehicle are limited. The primary market phase
source of uncertainty. In our problem setting, not only the customer ends at a certain cutoff time, e.g., the end of the day, prescribed by the
demand is uncertain but also the auction outcome (that depends on time the auction takes place.
decisions by the other carriers and the auctioneer). These two sources The secondary market phase describes the time horizon during
of uncertainty are relatively different and independent from each other which the auction is prepared, conducted, and evaluated. Multiple car-
which makes it difficult to design anticipatory approaches that take riers participate in this auction to trade requests among each other. We
both into account. Especially the auction outcome is hard to predict assume that the exchange is organized by an independent auctioneer in
because the carriers’ bids depend not only on the visible submitted the form of a combinatorial auction. All carriers are sellers and buyers
requests but also on the remaining larger number of requests that of requests and place their bids simultaneously without knowing the
are not revealed in the auction. This is by design as the fact that a other carriers’ bids (sealed-bid auction). As outlined by Berger and Bier-
combinatorial auction does not reveal sensitive information about other wirth (2010), the procedure of combinatorial auctions in transportation
carriers makes it particularly interesting for horizontal collaboration of follows five phases.
potentially competing carriers.
Concerning the research gap, we notice a clear focus on static Request selection Each carrier decides on the requests to trade in the
and deterministic problem settings in the collaborative vehicle routing auction.
literature. The few studies on dynamic settings focus on the interactions
of carriers in the auction without recognizing the potentially broader Bundling Based on the candidate set of selected requests, the auction-
optimization problem of each carrier that may cover, e.g., decisions on eer generates bundles containing subsets of those requests.
accepting or rejecting customer requests. On the other hand, the po-
tential of horizontal collaboration to utilize resources more efficiently Bidding Carriers submit bids for the bundles according to their -
has not yet been explored in the stochastic dynamic vehicle routing marginal costs for fulfilling the included requests.
literature. We conclude that a comprehensive approach is missing for
modeling the different types of sequential decisions each carrier faces Winner determination The auctioneer assigns the bundles to carriers
in a dynamic and collaborative setting. Such a model allows studying according to their bids in a way that the total fulfillment costs
the interaction between decisions facing the customer-related primary are minimized.
market and decisions on the secondary market when collaborating with
other carriers. Profit sharing The auctioneer distributes the profits of the collabora-
tion by determining the payments of individual carriers.
3. Problem description
At the end of the planning horizon, the carrier commits to satisfying
In the problem at hand, we consider a planning horizon, e.g., with a set of customer requests, composed of untraded accepted requests
a length of one day, that is divided into two phases. The first phase and auction-acquired requests. For this set of requests, the carrier must
concerns the primary market and comprises the time horizon in which determine the vehicle routes. However, the set of customer requests
customers request pickup and delivery orders that the carrier answers that can be feasibly served by the carrier is restricted by the maximum
by accepting or rejecting each of them. The second phase concerns the route duration and the maximum load capacity. Thus, we assume that
secondary market and begins after a cutoff time for the primary market there exists the alternative of outsourcing those requests that cannot be
phase is reached. In this phase, the carriers first select the – previously served for a – typically costly – penalty fee. Overall, the objective of the
accepted – requests they each want to trade in the combinatorial carrier is to accept and trade customer requests over the course of the
auction. The carriers then submit bids for bundles of requests based on planning horizon such that the profit is maximized. The profit results
which the auctioneer redistributes the requests. For the requests each from the revenues collected by accepting customer requests minus the
carrier commits to after both phases, the carrier needs to determine the costs for routing and outsourcing.
fulfillment in vehicle routes that is executed, e.g., on the next day. The In conclusion, the problem considered by a carrier entails decisions
timeline of the problem setting is visualized in Fig. 2, with the decisions that are dynamic, i.e., they must be made at multiple decision points
of each carrier marked in bold. over time, and are made under uncertainty, e.g., regarding their fu-
We now describe the elements of each of the two phases in more ture implications. This is due to stochastic elements of the problem,
detail, beginning with the primary market phase. Over the course particularly regarding the characteristics of the customer requests and
of this finite phase, stochastic customer requests arrive. Each request the outcome of the auction. The customer requests become known
features a pickup location, a delivery location, a load, and a revenue. dynamically during the planning horizon. Their time of arrival and
The carrier must decide on accepting or rejecting an individual request features such as pickup and delivery location are stochastic. While the
immediately when it arrives. While making those sequential decisions, winner determination and profit sharing are solved by the auctioneer
the carrier considers restrictions that result from the fulfillment of the in a deterministic way, they are stochastic for the individual carriers.

615
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

4. Auction-based exchange mechanism For the winner determination problem, the following notation is
considered, which is similar to that of Gansterer and Hartl (2016). A
A single-bid first-price combinatorial auction is considered in which set of carriers 𝛤 , a set of customer requests 𝐶, and a set of bundles 𝐵
each carrier participates as both a seller and a buyer. For describing the are given. The price 𝑃𝑏𝛾 a carrier 𝛾 demands to be paid for fulfilling
auction setting in more detail, we follow the framework of Berger and a bundle 𝑏 reflects the bid value. Parameter 𝑊𝑏𝑐 ∈ {0, 1} indicates
Bierwirth (2010). whether request 𝑐 is included in a bundle 𝑏 (𝑊𝑏𝑐 = 1) or not (𝑊𝑏𝑐 = 0).
In the request selection phase, each carrier selects the requests Finally, the binary decision variables 𝑦𝑏𝛾 ∈ {0, 1} indicate whether a
to put into the auction pool. The number of requests is determined bundle 𝑏 is allocated to a carrier 𝛾 (𝑦𝑏𝛾 = 1) or not (𝑦𝑏𝛾 = 0).
beforehand by the auctioneer to be equal for all carriers (parameter We depict the winner determination problem using the integer
𝑛𝛾 ). An auctioneer may want to impose such a restriction for two program (2)–(6).
reasons: (1) only a sufficient number of requests from different carriers ∑∑
min 𝑃𝑏𝛾 𝑦𝑏𝛾 (2)
can provide a certain level of total collaboration savings and (2) bal- 𝑏∈𝐵 𝛾∈𝛤
anced participation of carriers in the auction enables more equitable
subject to
redistribution and profit sharing. While several related works similarly
∑
impose this restriction (e.g., Berger & Bierwirth, 2010; Gansterer & 𝑦𝑏𝛾 ≤ 1 ∀𝛾 ∈ 𝛤 , (3)
Hartl, 2016), the interested reader is referred to Rüther and Rieck 𝑏∈𝐵
∑
(2022) for a study in which this restriction is relaxed. 𝑦𝑏𝛾 ≤ 1 ∀𝑏 ∈ 𝐵, (4)
Out of all requests in the auction pool, the auctioneer generates 𝛾∈𝛤
bundles containing one or multiple requests and reveals them to the ∑∑
𝑦𝑏𝛾 𝑊𝑏𝑐 = 1 ∀𝑐 ∈ 𝐶, (5)
carriers. The number of possible bundles is 2𝑛 − 1, with 𝑛 being the 𝑏∈𝐵 𝛾∈𝛤
number of requests in the auction pool. Note that a tight limit on
𝑦𝑏𝛾 ∈ {0, 1} ∀𝑏 ∈ 𝐵, 𝛾 ∈ 𝛤 . (6)
the number of requests selected by each carrier allows for offering all
possible bundles on which the carriers place their bids in the bidding The objective function (2) minimizes the total costs resulting from
phase. If more requests need to be traded, the number of offered the bundle allocation and the respective values of the winning bids.
bundles grows so large that the carriers would not be able to bid on Constraints (3) ensure that at most one bundle is allocated to each
every bundle within reasonable time. carrier while Constraints (4) enforce that every bundle is allocated to
For such cases, we propose a simple heuristic bundle generation not more than one carrier. Every request must be allocated exactly once
approach that is based on the findings of Gansterer and Hartl (2018a). according to Constraints (5). Finally, the domain of the binary variables
The approach generates a set of bundles 𝐵 to be offered in the auction is defined in (6).
using the desired number of bundles |𝐵| as the main input parameter. By obtaining the difference between the fulfillment costs after the
In accordance with the assumption that the carriers’ participation in the bundle reallocation and those before the auction from the carriers’
collaboration is relatively balanced, a desired bundle size |𝑏| (e.g., equal bids, total auction profits can be derived. Since we focus on relatively
(𝑛)
to 𝑛𝛾 ) must also be specified. Then, all |𝑏| bundles of size |𝑏| that can symmetric settings, in which all collaborating carriers are expected to
be generated from the 𝑛 requests are enumerated to yield the set 𝐵. ̄ provide similar contributions, the auctioneer distributes those total auc-
For each bundle 𝑏 ∈ 𝐵, ̄ a density value 𝜌𝑏 is calculated that is used as a tion profits to all participating carriers in an egalitarian way, i.e., each
measure for its fitness as a bundle offered in the auction. The density is carrier should profit equally from the redistribution. To achieve this,
computed as the average distance between the pickup (𝑝𝑐 ) and delivery each carrier’s difference between the fulfillment costs before and after
(𝑑𝑐 ) location of the requests 𝑐 in the bundle 𝑏 divided by the maximum the auction is derived from the bid values. Then, for each carrier,
distance among all requests to the bundle’s centroid 𝜎𝑏 , such that: payments to and from the auctioneer are determined such that this
∑ difference is equalized between carriers and budget balance is ensured
( 𝑐∈𝑏 𝑑𝑖𝑠𝑡(𝑝𝑐 , 𝑑𝑐 ))∕|𝑏|
𝜌𝑏 = ̄
∀𝑏 ∈ 𝐵. (1) (all payments need to even out to zero). Each carrier 𝛾 ∈ 𝛤 has
max𝑐∈𝑏 (𝑑𝑖𝑠𝑡(𝑝𝑐 , 𝜎𝑏 ) + 𝑑𝑖𝑠𝑡(𝑑𝑐 , 𝜎𝑏 )) fulfillment costs before the auction, 𝛽𝛾 , and fulfillment costs after the
redistribution of bundles of requests through the auction, 𝛼𝛾 , that may
All bundles are then sorted in a list according to their density values be smaller, equal, or larger than 𝛽𝛾 . The profit sharing now determines
in decreasing order. A number of bundles equivalent to the number a payment 𝜓𝛾 to (positive) or from (negative) each carrier, such that:
of carriers is selected in every iteration and added to set 𝐵 until the ∑
desired number |𝐵| is reached. In each iteration, the first unselected 𝛾∈𝛤 (𝛽𝛾 − 𝛼𝛾 )
𝛽𝛾 − 𝛼𝛾 + 𝜓𝛾 = ∀𝛾 ∈ 𝛤 . (7)
bundle from the sorted list is chosen and complementary bundles are |𝛤 |
chosen to be included by similarly searching the list. The bundles ∑
For non-negative total auction profits 𝛾∈𝛤 (𝛽𝛾 − 𝛼𝛾 ) ≥ 0, it holds
are complementary in a way that they contain other requests than that 𝛽𝛾 ≥ 𝛼𝛾 − 𝜓𝛾 , ∀𝛾 ∈ 𝛤 , i.e., each carrier is not worse off after
the bundles previously selected in the same iteration, thus creating the auction than before. In case a carrier’s fulfillment costs after the
partitions of non-overlapping bundles that enable feasible allocations redistribution (𝛼𝛾 ) are higher than before (𝛽𝛾 ), the payment 𝜓𝛾 will at
to the carriers. least compensate this difference. In Appendix B, we further provide a
In the bidding phase, all carriers place bids on all offered bundles. brief analysis on the value of profit sharing for the specific problem
We assume that carriers place their bids in a way that reflects the setting considered in this paper. For a more detailed study of the game-
marginal costs for fulfilling the requests in a bundle. Carriers also theoretic properties of this and similar types of combinatorial auctions,
place bids on bundles containing their own requests such that they still we refer to Gansterer et al. (2018).
might have to fulfill (some of) their own requests they submitted to the
auction pool. 5. Sequential optimization problem of each carrier
To determine the assignment of bundles to carriers according to
their bids, the auctioneer solves the winner determination problem. The The optimization problem of each carrier faces both the primary
objective of this problem is to assign at most one bundle to each carrier market (carrier to customer) and the secondary market (carrier to
such that all requests are assigned and the total costs are minimized. other carriers via auctioneer). As the integrated problem represents a
Due to those restrictions, a feasible allocation is always guaranteed and sequential optimization problem, we model it as a Markov decision
the carrier’s additional costs for fulfilling the allocated bundle exactly process (MDP). The Markov(ian) property of an MDP ensures that
match the respective bid value. transition probability and reward functions depend on the past only

616
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

through the current state of the system and the decision selected by the starting at the carrier’s depot 𝛿, visiting a sequence of pickup and
decision maker in that state (Bellman, 1957; Powell, 2011; Puterman, delivery locations, and ending at the depot. For an example case of
2014). three visited customer requests, a route could be denoted in the form
The MDP of the form 𝜃𝑘𝑚 = (𝛿, 𝑝0 , 𝑝1 , 𝑑1 , 𝑝2 , 𝑑0 , 𝑑2 , 𝛿). The set 𝐶𝑘𝑜 contains requests that are not
included in the route plan and thus are designated to be ‘‘outsourced’’.
MDP = {𝐾, 𝑆, 𝐴, 𝛺, 𝑅} (8)
Regarding the auction, set 𝐶𝑘𝑠 contains the requests that are selected
is composed of the following basic elements to depict the problem by the carrier in decision point 𝑘𝑠 to be submitted to the auction pool.
considered here. The decision points 𝐾 represent situations in which All bundles offered in the auction for bidding are depicted in set 𝐵
the decision maker (here: the carrier) needs to make decisions. A state with each bundle 𝑏 including at least one customer request 𝑐. Finally,
𝑆𝑘 in the state space 𝑆 describes the characteristics of the system at the carrier’s bid values for all bundles are determined in decision point
a decision point 𝑘 that are relevant for the carrier to make a decision 𝑘𝑠 and are contained in the bid vector 𝑃 . After the auction outcome
𝑎𝑘 from the decision space 𝐴. Exogenous information 𝛺 impacts the has been revealed, the MDP terminates in a final state 𝑆𝑓 , in which the
transition to a next state. We consider a reward function 𝑅(𝑆, 𝐴, 𝛺) final route plan 𝜃𝑓 and outsourcing set 𝐶𝑓𝑜 determine the fulfillment
describing the reward received after making a decision 𝑎𝑘 in a state 𝑆𝑘 . that can be implemented, e.g., on the next day.
Since the rewards in some decision points depend upon the outcome of
the auction, the rewards following those decisions are also impacted by 5.2. Decisions
exogenous information.
The transitions between states can be depicted in the form For each phase of the problem setting, different decisions are con-
𝑎𝑘 𝜔𝑘+1 sidered in the MDP.
← 𝑆𝑘𝑎 ←←←←←←←←←→
𝑆𝑘 ←←←←→ ← 𝑆𝑘+1 . (9)
Acceptance. In each decision point 𝑘𝑟 ∈ 𝐾𝑟 of the request acceptance
Making a decision 𝑎𝑘 in a state 𝑆𝑘 leads to a post-decision state 𝑆𝑘𝑎 , phase, the binary decision 𝑎𝑘𝑟 ∈ {0, 1} must be made to either accept
also denoted as the ‘‘deterministic transition’’. Exogenous information (𝑎𝑘𝑟 = 1) or reject (𝑎𝑘𝑟 = 0) an incoming request 𝑐 ∈ 𝐶𝑘𝑟 .
𝜔𝑘+1 received in a post-decision state 𝑆𝑘𝑎 leads to a next (pre-decision)
state 𝑆𝑘+1 , which is denoted as the ‘‘stochastic transition’’ due to the Selection. In the decision point 𝑘𝑠 , the decision vector 𝑎𝑘𝑠 = {0, 1}|𝐶𝑘𝑠 |
exogenous information being stochastic. describes the selection of requests that the carrier submits to the
Based on the reward function 𝑅(𝑆, 𝐴, 𝛺), the objective function (10) auction. For each accepted request 𝑐 ∈ 𝐶𝑘𝑠 , it contains the binary
of the problem maximizes the overall expected reward. decision of either selecting a request 𝑐 (𝑎𝑐𝑘 = 1) or not (𝑎𝑐𝑘 = 0).
𝑠 𝑠
[ ] The auctioneer sets the number of requests each carrier submits to the
∑ auction as a parameter, denoted by 𝑛𝛾 . This requirement is enforced as
𝜋
max E𝜔∈𝛺 𝑅(𝑆𝑘 , 𝐴𝑘 (𝑆𝑘 ), 𝜔) (10)
𝜋∈𝛱
𝑘∈𝐾 a constraint on the carrier’s decision vector, in the form
∑
A policy 𝜋 provides a decision function 𝐴𝜋𝑘 (𝑆𝑘 ) that returns a decision 𝑎𝑐𝑘 = 𝑛𝛾 . (11)
𝑠
𝑎𝑘 in each state 𝑆𝑘 . The optimization problem consists of finding the 𝑐∈𝐶𝑘𝑠
optimal policy 𝜋 ∗ that maximizes the objective function value.
Bidding. In the decision point 𝑘𝑏 , the decision vector 𝑎𝑘𝑏 = R|𝐵|
Since the considered problem setting covers multiple different
describes the bids for all bundles 𝐵 offered in the auction. A real-valued
phases of decisions that a carrier must consider, we introduce a more
bid must be provided for each bundle 𝑏 ∈ 𝐵.
detailed description, structured by the elements of the MDP, in the
following. At the end of this section, a small example network is Routing. All previously described decisions – acceptance, selection, and
provided to visualize the general outline of the MDP. We further build bidding – have implications on the later executed fulfillment and the
upon the descriptions in this section when introducing the heuristic corresponding fulfillment costs. On the other hand, all those decisions
solution approaches in Section 6. can only be made in an informed way if their implications are already
considered in the decision-making process. Thus, it is necessary to not
5.1. Decision points and states only determine a plan for fulfillment at the very end of the planning
horizon. Rather, the carrier maintains a preliminary route plan 𝜃𝑘 and
According to the phases of the problem setting, the decision points outsourcing set 𝐶𝑘𝑜 in the states 𝑆𝑘 of all decision points 𝑘 ∈ 𝐾. Since
𝐾 = 𝐾𝑟 ∪ 𝑘𝑠 ∪ 𝑘𝑏 can be divided into a sequence of decision points the vehicle routing problem, of which an instance would need to be
𝐾𝑟 = {0, 1, … , 𝑘𝑚𝑎𝑥 } for arriving customer requests, a single decision solved in every decision point, is of combinatorial nature on its own,
point 𝑘𝑠 representing the request selection phase before entering the the decision space of the MDP grows excessively large if all possible
auction, and a single decision point 𝑘𝑏 representing the bidding phase routing decisions are considered explicitly in every decision point. To
of the auction. The primary market phase ends after the last incoming resolve this, we introduce heuristic approaches in Section 6 to update
customer request in decision point 𝑘𝑚𝑎𝑥 , that can still be considered the preliminary route plan and outsourcing set. For the sake of clarity
before the auction starts, is answered. This makes the planning horizon and for providing a link to related literature on static deterministic
finite. problem settings, the routing problem, that is a variant of the multi-
We define each state 𝑆𝑘 = (𝑡𝑘 , 𝐶𝑘𝑟 , 𝐶𝑘 , 𝜃𝑘 , 𝐶𝑘𝑜 , 𝐶𝑘𝑠 , 𝐵, 𝑃 ) in a decision vehicle, one-to-one pickup and delivery problem, is formally described
point 𝑘 ∈ 𝐾 to be characterized by the following features, that equally as a mixed integer linear program in Appendix A. The solution value
apply to the post-decision states 𝑆𝑘𝑎 . The point of time when a decision of this problem yields the total costs for fulfilling a set of pickup and
point 𝑘 is reached is denoted as 𝑡𝑘 . The state also contains information delivery requests. The constraints restrict the decision space of the
regarding customer requests, with each request 𝑐 featuring a pickup routing decisions in the MDP.
location 𝑝𝑐 , a delivery location 𝑑𝑐 , a volume 𝑞𝑐 , a service time 𝑠𝑐 , and
a revenue 𝑟𝑐 . Incoming customer requests in a decision point 𝑘 are 5.3. Exogenous information and transition function
included in 𝐶𝑘𝑟 . The set 𝐶𝑘 comprises the set of previously accepted
customer requests 𝑐 ∈ 𝐶𝑘 . At the beginning of the planning horizon (𝑘 = 0), the MDP’s initial
We assume that, in each decision point 𝑘, a preliminary, feasi- state 𝑆0 is defined by 𝑡0 = 0 and 𝐶0𝑟 = 𝐶0 = 𝜃0 = 𝐶0𝑜 = 𝐶0𝑠 =
ble route plan 𝜃𝑘 and an outsourcing set 𝐶𝑘𝑜 are maintained. This 𝐵 = 𝑃 = ∅. In all decision points 𝑘 ∈ 𝐾, decisions 𝑎𝑘 are made
is inspired by the route-based MDP formulation proposed by Ulmer that impact the post-decision state 𝑆𝑘𝑎 . Those decisions also trigger
et al. (2020). The route plan prescribes a route 𝜃𝑘𝑚 for each vehicle 𝑚, an update of the preliminary route plan 𝜃𝑘 and the outsourcing set

617
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

𝐶𝑘𝑜 . After the decision has been made, exogenous information 𝜔𝑘+1 is Acceptance. The reward for accepting (𝑎𝑘𝑟 = 1) a request 𝑐 equals its
observed, followed by a stochastic transition towards the next decision revenue 𝑟𝑐 minus the marginal costs for serving the request. These
point 𝑆𝑘+1 = 𝑆 𝑀 (𝑆𝑘 , 𝑎𝑘 , 𝜔𝑘+1 ) according to a transition function 𝑆 𝑀 . marginal costs can be derived from the fulfillment costs of the pre-
Since different kinds of information become available in the different liminary route plan and outsourcing set of the post-decision state
phases of the problem, we again structure the more-detailed description 𝑆𝑘𝑎 , i.e., where the new request is already inserted, compared to the
of the transitions based on the types of decision points. fulfillment costs of the pre-decision state 𝑆𝑘 . No reward is collected for
Acceptance. In the request acceptance phase, exogenous information is rejecting (𝑎𝑘𝑟 = 0) a request.
observed in the form of incoming customer requests. The arrival of a Selection. The reward for request selection following a decision 𝑎𝑘𝑠 =
request 𝑐 with its specific features triggers a new decision point 𝑘𝑟 . The {0, 1}|𝐶𝑘𝑠 | depends on the individual requests 𝑐 that are selected for the
state information 𝑆𝑘 is updated to contain the incoming request 𝑐 in
auction, i.e., for which 𝑎𝑐𝑘 = 1. Since those requests must no longer
set 𝐶𝑘𝑟 = {𝑐} and the time point 𝑡𝑘 at which the request has arrived. 𝑠
be fulfilled (as of this time point), the marginal costs that are saved
After a decision 𝑎𝑘𝑟 ∈ {0, 1} has been made to accept or reject the
represent the reward. Similar as for the acceptance decision, we can
request, we end up in a post-decision state 𝑆𝑘𝑎 . The following changes
obtain this cost difference from comparing the preliminary route plans
of a state 𝑆𝑘 to a post-decision state 𝑆𝑘𝑎 also hold until the next state
and outsourcing sets before and after the decision.
𝑆𝑘+1 is observed. If the request has been accepted (𝑎𝑘𝑟 = 1), the set
of accepted requests is updated to 𝐶𝑘+1 = 𝐶𝑘 ∪ 𝐶𝑘𝑟 , else 𝐶𝑘+1 = 𝐶𝑘 . In Bidding. The reward following a bidding decision 𝑎𝑘𝑏 = R|𝐵| depends
case of acceptance and if insertion is feasible (according to the heuristic on both the decision itself, i.e., the bid values, and the stochastic
routing policy), the preliminary route plan 𝜃𝑘 is updated to include transition, i.e., the auction outcome. Assuming that a carrier bids
the new request. In case of acceptance and if insertion is infeasible, truthfully, the marginal fulfillment costs of the allocated bundle 𝑏∗
the outsourcing set is updated to include the request, i.e., 𝐶𝑘+1 𝑜 =
𝑜 𝑟 𝑠
exactly matches its bid value 𝑃𝑏 . Note that the carrier may also be
𝐶𝑘 ∪ 𝐶𝑘 . The sets 𝐶𝑘 and 𝐵 are unchanged and remain empty during
allocated the bundle that contains exactly those requests that were
the acceptance phase. After a decision has been made, the next state
previously selected in the request selection decision, basically offsetting
𝑆𝑘+1 is entered after a new incoming request is observed as exogenous
the cost savings obtained earlier. Thus, the stochastic element of the
information 𝜔𝑘+1 (stochastic transition).
reward depends purely on the payments awarded or demanded by the
Selection. The single decision point for request selection 𝑘𝑠 is entered auctioneer that are, however, influenced by the carriers’ bids and the
when the cutoff time 𝑡𝑚𝑎𝑥 for the acceptance phase is reached. The profit sharing mechanism.
new state 𝑆𝑘𝑠 thus contains the time point 𝑡𝑘𝑠 = 𝑡𝑚𝑎𝑥 and inherits all
other variables unchanged from the state of the last decision point 𝑘𝑟 5.5. Example
with 𝑡𝑘𝑟 < 𝑡𝑚𝑎𝑥 . Triggered by a decision 𝑎𝑘𝑠 = {0, 1}|𝐶𝑘𝑠 | , the selected
requests 𝑐 for which 𝑎𝑐𝑘 = 1 are moved to the (previously empty) Finally, we depict a small example of an MDP in Fig. 3. Note that
𝑠
request selection set 𝐶𝑘𝑠 in the post-decision state 𝑆𝑘𝑎 . Following this, while this network representation – inspired by Goodson et al. (2017)
𝑠 𝑠
the requests 𝑐 ∈ 𝐶𝑘 are removed from the route plan 𝜃𝑘𝑠 or the – has similarities to a decision tree, it is not an actual tree due to
𝑜
outsourcing set 𝐶𝑘 , respectively. Note that the set of accepted requests
𝑠 branches rejoining in downstream nodes. The nodes of the network
𝐶𝑘𝑠 remains unchanged to reflect the revenue collected from those represent states 𝑆𝑘 (squares) and post-decision states 𝑆𝑘𝑎 (circles). The
requests. The stochastic transition comprises the request selection by arcs represent viable decisions 𝑎𝑘 in a state leading to a post-decision
the other carriers and the bundle generation by the auctioneer. Finally, state (solid arrows) and exogenous information 𝜔𝑘+1 leading from a
the exogenous information 𝜔𝑘𝑠 reveals the set of bundles 𝐵 offered in post-decision state to another state (dashed arrows). In this example,
the auction and leads to the next decision point 𝑘𝑏 , representing the
we consider three decision points in the acceptance phase (𝑘𝑟 ), one for
bidding phase.
the selection decision (𝑘𝑘𝑠 ), and one for the bidding decision (𝑘𝑘𝑏 ). For
Bidding. The state 𝑆𝑘𝑏 of the decision point for bidding 𝑘𝑏 thus includes the sake of simplicity, routing decisions and rewards are not depicted
the revealed set of bundles 𝐵. Making a decision 𝑎𝑘𝑏 = R|𝐵| fills the here. Also, we restrict the network to show only the immediate parts
vector 𝑃 in the post-decision state 𝑆𝑘𝑎 with all bid values of the carrier, resulting from a respective chosen decision and materializing exoge-
𝑏
one for each bundle. To generate a bid, the requests of a bundle are nous information (arrows marked in bold), thereby omitting other parts
inserted into the preliminary route plan 𝜃𝑘𝑏 or outsourcing set 𝐶𝑘𝑜 (small gray arrows).
𝑏
to yield a bundle-specific route plan 𝜃𝑏 and outsourcing set 𝐶𝑏𝑜 for Following the decision points of the example from left to right,
each bundle 𝑏 ∈ 𝐵. After the carrier’s bidding decision, the stochastic the first incoming request is accepted (𝑎0 = 1) and the exogenous
transition comprises the bids by the other carriers, followed by the information 𝜔1 reveals a new state 𝑆1 with another incoming request.
auctioneer’s winner determination and profit sharing procedure. The This request is also accepted (𝑎1 = 1) and 𝜔2 reveals another incoming
exogenous information 𝜔𝑘𝑏 reveals the auction outcome, i.e., the bundle request in 𝑆2 . This request, however, is rejected (𝑎2 = 0), e.g., due
𝑏∗ allocated to the carrier and the payments, leading to a final state 𝑆𝑓 . to insufficient route capacity. As the time horizon expires after this
The final route plan 𝜃𝑓 and outsourcing set 𝐶𝑓𝑜 , that together determine last request, 𝜔𝑘𝑠 reveals state 𝑆𝑘𝑠 ahead of the request selection. If we
the total fulfillment costs, are updated to include the requests of the assume the auctioneer requires 𝑛𝛾 = 1 in our example, a selection of
allocated bundle 𝑏∗ . In this way, they equal the bundle-specific route one request needs to be made from the set of two accepted requests.
plan (𝜃𝑓 = 𝜃𝑏∗ ) and outsourcing set (𝐶𝑓𝑜 = 𝐶𝑏𝑜∗ ) generated for the
The chosen decision 𝑎𝑘𝑠 = (1, 0) implies that the first request is
bidding decision.
selected while the second request is not. The exogenous information
𝜔𝑘𝑏 comprising the request selection of other carriers and the bundle
5.4. Rewards
generation of the auctioneer reveals state 𝑆𝑘𝑏 ahead of the request
Overall, each carrier facing this sequential optimization problem selection. The set of bundles 𝐵 = {(0), (1), (0, 1)} offered in this state
aims to maximize the expected profit based on the revenue from contains combinations of a request 0 selected by the carrier and a
accepted requests and the costs caused by fulfilling the requests via request 1 selected by another carrier. Of the range of possible decision
routing or outsourcing. Broken down to the sequential decisions, a options containing real-valued bids for the offered bundles (depicted
decision 𝑎𝑘 in a state 𝑆𝑘 is associated with a reward 𝑅(𝑆𝑘 , 𝑎𝑘 , 𝜔𝑘+1 ) that with dotted circles), the bidding decision 𝑎𝑘𝑏 = 𝑃 = (7, 4, 24) is made.
may be impacted by exogenous information 𝜔𝑘+1 materializing ahead The vector 𝑃 specifies a bid of 𝑃0 = 7 for request 0, 𝑃1 = 4 for
of the next decision point 𝑘 + 1. The calculation of the rewards can be request 1, and 𝑃2 = 24 for the bundle containing both requests. The
distinguished for the different types of decision points, in all of which superadditivity of the bids, i.e., 𝑃2 ≥ 𝑃0 + 𝑃1 , may be caused by the
the fulfillment costs due to routing or outsourcing play a role. penalty (here: 𝑓𝑖 = 20) the carrier would need to pay for acquiring both

618
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 3. MDP example.

requests and not being able to serve one of them due to route capacity Balanced The request is assigned to the route that is the shortest after
restrictions. After the auction outcome is determined by 𝜔𝑓 , the final inserting the request. This policy follows the intuition of keeping
state 𝑆𝑓 is entered that specifies the fulfillment on the next day. the remaining slack balanced among all routes to allow for more
flexibility in inserting future requests.
6. Solution approaches
Finally, if there exists no feasible insertion position for a request in any
Due to the curses of dimensionality, the described MDP cannot
route, the request is added to the outsourcing set.
be solved to optimality in a straightforward way, e.g., using dynamic
programming. Therefore, we approach this problem by designing poli-
cies that provide heuristic solutions. According to the classification 6.2. Acceptance
of Soeffker et al. (2022) and Powell (2011), our solution approach
can be denoted as a type of policy function approximation, as it ex- For a carrier’s decision of whether to accept a customer request or
ploits analytically derived, problem-specific knowledge that is used for not, we assume that a request must be accepted if it can be feasibly
defining decision rules. The following subsections are dedicated to the served in any of the routes. Carriers are permitted to reject a request
different decisions of the MDP, for each of which we present different
that cannot be served in a route given the current situation, however,
policies. We begin with describing the approaches for solving vehicle
they are also permitted to still accept such a request. In the subsequent
routing problems, as they must be considered for making substantiated
secondary market phase, the auction outcome may provide them with a
decisions in all decision points.
solution to outsource this request to other carriers or to exchange other
6.1. Routing requests in a way that ‘‘makes room’’ to serve this request. Nevertheless,
the auction outcome is always dependent on the other participating
Solving the routing problem can be divided into the assignment carriers, specifically on the requests they submit to the auction pool
decision for assigning the request to one of the routes and the sequencing and the bids they place on bundles.
decision for determining the order of customer visits in a route. For To recognize the implications of the combinatorial auction already
making the sequencing decision for each vehicle, we use a cheapest during the request acceptance phase, we design a number of policies
insertion policy. Since the customer requests in the considered problem that consider strategic request acceptance. All the policies accept all
setting are pairs of pickup and delivery locations, the two locations requests that can be served in routes. For an incoming request that
need to be visited by the same vehicle and precedence constraints cannot be inserted, the policies prescribe the acceptance decision in
(pickup before delivery) need to be respected. In addition, the restricted
the following way.
route duration and load capacity of a vehicle must not be exceeded.
The full set of constraints is depicted in the vehicle routing formulation
Feasible Representing a benchmark policy, the carrier accepts only
(A.2)–(A.15) presented in Appendix A. For each route, we check all
those requests that can be feasibly served in routes. As we
insertion options for the pair of pickup location and delivery location
assume that the revenue for a request is always smaller than
for feasibility and identify the cheapest insertion option among all of
them. the penalty fee for outsourcing, this policy represents myopic
After identifying the cheapest insertion option for each route, a decision-making.
request must be assigned to one of the eligible routes for which a
feasible insertion option could be found. For this assignment decision, Next The carrier accepts the next requests that cannot be served in
we consider the following different policies: routes in their order of arrival up to a certain number of requests
(denoted by the threshold 𝜖). Here, as in all following policies,
Random Representing a benchmark policy, the request is assigned the carrier accepts a negative immediate reward for accepting a
randomly to any of the routes.
request with a revenue smaller than its marginal fulfillment cost
Cheapest The request is assigned to the route with the lowest insertion (which equals the penalty fee for outsourcing).
costs for inserting the request, minimizing the overall detour
that needs to be taken. This equals myopic decision-making to Easy The carrier accepts those requests that cannot be served in routes
maximize the immediate reward by minimizing the marginal but have a pickup location 𝑝𝑐 and a delivery location 𝑑𝑐 that are
fulfillment costs. within a certain vicinity 𝜖 to each other, i.e., if 𝑑𝑖𝑠𝑡(𝑝𝑐 , 𝑑𝑐 ) ≤ 𝜖.

619
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Close The carrier accepts those requests that cannot be served in up with a final route plan after notification of the auction outcome.
routes but have a pickup location 𝑝𝑐 or a delivery location 𝑑𝑐 Changing the route plan before fulfillment starts would technically be
within a certain vicinity 𝜖 to a depot 𝛿𝛾 of any carrier 𝛾, i.e., if possible (as is indicated in the problem description, e.g., in Fig. 2), but
∃𝛾 ∈ 𝛤 with 𝑑𝑖𝑠𝑡(𝑝𝑐 , 𝛿𝛾 ) ≤ 𝜖 or 𝑑𝑖𝑠𝑡(𝑑𝑐 , 𝛿𝛾 ) ≤ 𝜖. the lack of any new information would never lead to a modification of
the route plan.
Close+Easy The carrier accepts those requests that cannot be served
in routes but have a pickup location 𝑝𝑐 and a delivery location 7. Numerical experiments
𝑑𝑐 within a certain vicinity 𝜖 to a depot 𝛿𝛾 of any carrier 𝛾, i.e., if
∃𝛾 ∈ 𝛤 with 𝑑𝑖𝑠𝑡(𝑝𝑐 , 𝛿𝛾 ) + 𝑑𝑖𝑠𝑡(𝑑𝑐 , 𝛿𝛾 ) ≤ 𝜖. We conduct a set of numerical experiments to provide insights into
the interaction of the primary and the secondary market by comparing
In the four acceptance policies that consider overbooking (Next, different route-assignment and acceptance policies. In this section, we
Easy, Close, and Close+Easy), the number of requests that can be first describe the instances and then report the results.
inserted into the outsourcing set during the acceptance phase is further
limited to the number of requests 𝑛𝛾 that can be selected for the 7.1. Instances
auction, such that |𝐶𝑘𝑜 | ≤ 𝑛𝛾 holds for every 𝑘 ∈ 𝐾𝑟 . In this way,
overbooked requests can only be accepted if they, potentially, can be The artificial instances are generated in the following way. Three
traded in the auction. Referring again to the terminology of the class carriers are considered that each have a circular service area with
of policy function approximation, the threshold parameter 𝜖 can be one depot in the center. To reflect the spatial boundary conditions
used to manipulate the respective policy function of these policies. In of a realistic setting for collaborative vehicle routing, four instance
this paper, we assume that the parameter value is set by the carrier, types are generated that vary in the service areas’ size and overlap.
e.g., based on analytical findings or experience, and we evaluate a The assumptions are in line with the instances used in collaborative
selection of parameter values in the numerical experiments (Section 7). vehicle routing literature (e.g., Berger & Bierwirth, 2010; Gansterer &
To achieve a respective policy’s best performance, the parameters may Hartl, 2018a; Gansterer, Hartl & Sörensen, 2020) and based on insights
also be tuned. However, finding the best parameter value bears the from real-world data, e.g., according to the study of Montoya-Torres
challenge of solving a stochastic optimization problem that maximizes et al. (2016) on a collaboration for goods delivery in Bogotá. First,
the expected reward (Powell, 2011, Chapter 6.3). the instance types vary in the distance between the depot locations of
the three carriers with the smaller distance providing a larger overlap
6.3. Request selection between the carriers’ service areas promising higher collaboration po-
tential. The distance 𝐷 between each pair of depot locations is set to
A carrier can pursue different strategies to select requests that either 𝐷 = 10 km or 𝐷 = 20 km. Second, two sizes of service areas with
should be submitted to the auction pool. For a deeper investigation a radius 𝑅 around the central depot of either 𝑅 = 10 km or 𝑅 = 20 km
of different request evaluation strategies that, e.g., focus on spatial are considered with smaller service areas promising vehicle routes with
features of requests, we refer to Gansterer and Hartl (2016). In this more customer visits. The resulting four combinations are visualized in
particular problem setting, the revenue for accepting requests has Fig. 4.
already been collected by carriers ahead of the auction, and we assume Since, in contrast to most collaborative routing literature, we ad-
that all requests are of equal value. Thus, exchanges in the auction are ditionally consider a dynamic request acceptance phase, the demand
purely made based on their respective marginal fulfillment costs for the arrival process is set up to reflect typical instances in stochastic dy-
carrier that holds the request. Carriers focus on getting rid of unsuitable namic vehicle routing literature. The demand of each carrier consists
requests to ‘‘make room’’ for requests offered in the auction that can of customer requests 𝑐 that arrive over a Poisson distribution at each
be served more efficiently. Based on this reasoning, each carrier offers time point 𝑡 within the limited time horizon of 𝑡𝑚𝑎𝑥 = 480 minutes.
those requests with the largest marginal costs. The marginal costs equal The arrival rate per minute is set to 𝜆 = 50∕480 such that each carrier
the cost savings from removing the pickup and the delivery location receives 50 specific customer requests in expectation during the time
of a request from the respective tour. Note that this policy equals horizon. We generate 10 demand instances per instance type. For each
myopic decision-making to maximize the immediate reward by saving request 𝑐, the pickup location 𝑝𝑐 and the delivery location 𝑑𝑐 are drawn
the marginal fulfillment costs for the most expensive requests. from a uniform distribution over the carrier’s service area. A service
time of 𝑠𝑐 = 10 minutes and a volume of 𝑞𝑐 = 1 load unit are considered
6.4. Bidding for every request. Finally, we consider different settings for the revenue
per request of 𝑟𝑐 = {30, 35, … , 50} cost units, but all requests in the same
We assume that the carriers bid truthfully on the bundles offered instance contain equal revenue.
in the auction. In this way, the value of their bids represent the Each carrier operates three vehicles that travel with an average
actual marginal costs of serving the requests of a bundle. Strategic bid- speed of 𝑣 = 30 km/h. The travel times 𝑡𝑖𝑗 between 𝑖 and 𝑗 are thus
ding, i.e., overestimating or underestimating the value of a bundle, is obtained using Euclidean distances and the vehicle speed. The route
assumed to not bear any advantages for the individual carriers as it neg- duration limit of each vehicle is set to 𝐿 = 480 minutes and the
atively affects the total collaboration gains that are distributed equally maximum load capacity is set to 𝐶 = 20 load units. We consider a
among carriers. For a more nuanced discussion of truthful vs. untruthful routing cost of 𝑐𝑖𝑗 =1 cost unit per minute of travel time 𝑡𝑖𝑗 . The penalty
bidding, we refer to Gansterer and Hartl (2018a). They show in an fee for outsourcing is set to 𝑓𝑖 = 50 cost units per request. With this
experimental comparison using a similar exchange mechanism that setting, the penalty fee is never exceeded by the revenue of a request
finding a profitable untruthful bidding strategy is hard. The bid values (as this would render overbooking always profitable), and it always
are generated by inserting the requests of a bundle into the preliminary exceeds the average marginal routing costs obtained in our instances.
route plan or outsourcing set. Since there are no future decisions after Regarding the auction, the following parameter settings are consid-
the bidding decision, the myopic route-assignment policy Cheapest is ered. The number of requests selected by each carrier to be submitted
used for the insertion of requests. In case of multiple requests in a to the auction pool is set to either 𝑛𝛾 = 4 or 𝑛𝛾 = 8. In the case of 𝑛𝛾 = 4,
bundle, the requests are inserted one by one in the order the requests all possible bundles are generated out of the 𝑛 = 12 requests submitted
were originally received. If a request cannot be inserted into any of by all three carriers, resulting in a total of 2𝑛 − 1 = 4095 offered bundles
the routes, it is outsourced. As the carriers always maintain a tentative per instance. In the case of 𝑛𝛾 = 8, more than 16 million bundles
route plan – including for evaluating all bidding decisions – they end could potentially be generated. Since this number is computationally

620
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 4. Depot locations and service areas (dashed line: 𝑅 = 10 km; solid line: 𝑅 = 20 km) of different instance types.

Table 1 be inserted into the preliminary route plan using the respective route-
Experimental setup. assignment policy. The results show that more requests can be accepted
Route-assignment policies Acceptance policies Overbooking settings if requests are inserted into routes in a more balanced way. While the
Random Feasible All carriers route-assignment policy Cheapest (mean: 67.82%; standard deviation:
Cheapest Next: 𝜖 = {1, 2, 3, 4} requests One carrier 9.18%) performs even slightly worse than the Random policy (68.05%;
Balanced Easy: 𝜖 = {2.5, 5.0, 7.5} km Two carriers 9.52%), the Balanced policy (74.52%; 8.65%) outperforms both clearly.
Close: 𝜖 = {2.5, 5.0, 7.5} km
Fig. 6 provides a visual explanation for why the Balanced policy
Close+Easy: 𝜖 = {10, 15, 20} km
performs better. We focus on one example instance and the three
vehicle routes of one carrier. The figures show the slack, i.e., the
remaining time up to the route duration limit 𝐿 = 480 minutes, of each
intractable in the bidding phase, we employ the heuristic bundle gen- route (lines in different colors) over the time points of the planning
eration approach presented in Section 4. The approach is set up such horizon with a total length of also 480 minutes. Note that this depiction
that it selects |𝐵| = 1000 bundles containing exactly |𝑏| = 8 requests only focuses on the time slack, but the load capacity further restricts
each. Finally, all experiments are implemented using Python 3.10 and the routes. Step-wise reductions of the slack can be observed when a
run on a PC with an Intel Core i5-1145G7 CPU and 16 GB of RAM. request is accepted, indicated by a black dash at the top of each figure,
and inserted into a route following the respective route-assignment
policy. Rejection of a request, indicated by a gray dash, does not alter
7.2. Results the routes.
In the figures, it can be observed that the choice into which route
In the presentation of the experimental results, we compare the a request is inserted is crucial for the routes’ utilization over time
policies described in Section 6 in the following way. First, we evaluate and, thus, the possibilities for inserting more requests, especially at
the three different route-assignment policies – Random, Cheapest, and later time points. The Random policy – as expected – does not show
Balanced – for all instances and in combination with the acceptance a distinct pattern regarding the utilization (Fig. 6(a)). Applying the
policy Feasible. Then, we choose the best-performing route-assignment Cheapest policy (Fig. 6(b)) results in routes being filled with requests
policy and perform an extensive set of experiments on all instance types one by one, leading to fewer insertion options and fewer accepted
to compare the five acceptance policies – Feasible, Next, Easy, Close, requests in later time points. In contrast, the Balanced policy (Fig. 6(c))
and Close+Easy. For each of the acceptance policies with overbooking, satisfies the intended purpose of balancing the utilization between the
three different settings for the threshold 𝜖 are evaluated to investigate different routes which leads to more requests being accepted, also at
later time points.
the sensitivity regarding this parameter. After preliminary experiments,
Another objective of a suitable route-assignment policy in our prob-
we have selected these particular settings as they appropriately repre-
lem is to provide cost-efficient route plans in terms of fulfillment costs.
sent the range of possible solutions over all instance types and, thus,
Thus, in Fig. 7, we compare the route-assignment policies regarding
improve interpretability of the results. For the Easy and Close policies, the costs of their generated route plans. For each policy, we further
in both of which the threshold refers to the distance between two loca- distinguish between the costs of the preliminary route plan ahead of
tions, the same threshold settings are used. Larger settings are used for making the request selection (𝜃𝑘𝑠 ), i.e., before auction, and those of
the Close+Easy policy, in which the threshold refers to the sum over two the final route plan (𝜃𝑓 ), i.e., after auction (considering 𝑛𝛾 = 4). The
distances. Finally, we analyze the impact of overbooking on the profits average costs per request are reported, based on the total routing costs
of the collaborating carriers given different revenues per request. For and the number of accepted requests. Since we focus on the acceptance
this reason, we distinguish between all carriers (symmetric setting), one policy Feasible in these experiments, penalty costs for outsourcing do
carrier or two carriers (asymmetric settings) that accept more requests, not apply.
focusing on the best-performing acceptance policy Close+Easy. The The results show that the routes obtained by the Balanced policy are
variables of this numerical study are summarized in Table 1. Further, more cost-efficient than those obtained by the Random and Cheapest
we provide a brief analysis on the value of the profit sharing mechanism policy, both before and after the auction. When comparing the route
– that is not the main focus of this paper – in Appendix B. costs before the auction with those after the auction, the observed cost
savings are smallest with the Balanced policy. This is due to the before-
auction routes being already relatively well balanced and almost fully
7.2.1. Route-assignment policies utilized. This is not the case using the Random and the Cheapest policy,
In this section, we compare the performance of the three route- which is why redistribution of requests through the auction can provide
assignment policies. Average results for all instances of the four types larger cost savings. Since we are interested in a route-assignment policy
are reported. In Fig. 5, the percentage of accepted requests among that both contributes to collecting revenue by inserting many accepted
the incoming requests for all carriers is shown. The acceptance policy requests and minimizes fulfillment costs, we choose the Balanced policy
Feasible is used, i.e., requests are only accepted if they can feasibly to be used in all further experiments.

621
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 5. Acceptance ratio (mean and standard deviation) of different route-assignment policies.

Fig. 6. Slack of 3 individual routes over the time horizon for an example instance.

7.2.2. Acceptance policies In Table 2, the number of overbooked requests per carrier is sum-
The remaining part of the experimental results is concerned with marized for all instance types and the acceptance policies Easy, Close,
the acceptance policies and, particularly, the impact of overbooking. In and Close+Easy with 𝑛𝛾 = 4. Those policies use a threshold 𝜖 that
this section, we analyze the sensitivity to different parameter settings is dependent on the pickup and delivery locations of the incoming
if all carriers follow the same acceptance policy. First, we evaluate the requests. The Close and Close+Easy policies further consider the depot
number of overbooked requests. Then, we focus on the collaboration locations of all carriers, which also differ between instance types. As
savings that can be obtained in the auction using different acceptance expected, it can be observed that extending the distance-based thresh-
policies. Since the trading of requests in the auction is purely based old results in more requests being accepted by all policies. The number
on costs, the analysis in this section disregards the additional revenue of overbooked requests achieved by the chosen parameter values also
from accepting more requests. Later in Section 7.2.3, the impact on the roughly covers the feasible range from 0 to 𝑛𝛾 = 4 (being the number
overall profit is considered. of requests selected for the auction). The Feasible and the Next policy

622
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 7. Average costs per request with different route-assignment policies before and after the auction.

Table 2 overbooking using any acceptance policy increases the relative savings
Number of overbooked requests per carrier for different acceptance policies and
achieved by the auction. This is due to the high penalty costs that may
instance types.
be saved through the redistribution of requests. Performing too much
Policy 𝜖 Instance type
overbooking, however, diminishes the collaboration savings. If all car-
D10-R10 D10-R20 D20-R10 D20-R20
riers enter the auction with too many requests, efficient redistribution
2.5 km 0.33 0.37 0.33 0.37 is impossible and the auction almost resembles a zero-sum game.
Easy 5.0 km 1.20 0.97 1.20 0.97
7.5 km 1.67 2.17 1.67 2.17
7.2.3. Impact of overbooking
2.5 km 1.23 1.77 0.57 0.90
Close 5.0 km 2.60 3.90 1.90 3.20 In this section, we investigate the overall profit of the carriers
7.5 km 2.73 4.00 2.67 3.90 if overbooking is performed. In general, accepting more requests in-
10 km 1.03 0.67 0.83 0.17 creases the revenue and also the preliminary fulfillment costs of a
Close+Easy 15 km 2.57 2.20 2.40 1.20 carrier. The carrier’s profit, however, is impacted by the specific dif-
20 km 2.80 3.73 2.80 3.10 ference between revenue and costs as well as by the auction outcome.
We start with a first analysis of the symmetric setting, in which we
assume that all carriers follow the same acceptance policy as a strategy
are not considered here, as the number of overbooked requests is either they may have obtained from, e.g., observing the market behavior in
zero (Feasible) or any number set by a parameter (Next ). previous periods. In a second analysis, we compare those results with
In Table 3, the collaboration savings for all acceptance policies asymmetric settings in which only a single carrier or two carriers use
with their specific threshold settings and instance types are depicted. an acceptance policy with overbooking. To avoid any influence from a
heuristic bundle generation, the analysis in this section is restricted to
Both instances with 𝑛𝛾 = 4 and all generated bundles as well as
the instances with 𝑛𝛾 = 4 for which all bundles could be enumerated.
instances with 𝑛𝛾 = 8 using the heuristic bundle generation approach
are considered. The collaboration savings are defined as the relative Symmetric setting. In Fig. 8, the impact on profit is reported for the
improvement of the fulfillment costs after the auction compared to acceptance policies with their specific threshold settings and for the
those before the auction for all carriers in total. From the results of the five different settings of revenue per request. For reasons of clarity, in
Feasible policy, the effect of the instance type can be easily observed, this figure we leave out the Next policy with 𝜖 = 4 that performed
which also holds for all other policies. The collaboration savings are poorly. The impact on profit is defined as the relative improvement or
larger for instances with comparably larger service areas, in which the deterioration in percentage compared to the profits obtained for the
marginal costs for serving individual requests are higher. The D10-R20 benchmark acceptance policy Feasible over the respective instances on
instances with comparably more overlap between the carriers’ service average. For this comparison, we first focus on the D10-R20 instances,
areas, i.e., with smaller distance between depots, allow for the largest as these provide the largest overlap of carriers’ service areas, but the
savings. Nevertheless, small collaboration savings can be achieved even results for other instance types show a similar tendency. The different
in the D20-R10 instances that do not provide any overlap. line styles (dotted, dashed, dash-dotted, solid) denote the different
The choice and parameterization of the acceptance policy has a policies while the shade indicates the threshold setting.
clear impact on the collaboration savings, that range from 1.52% to The results show a considerable impact of overbooking on the
10.78% with 𝑛𝛾 = 4 and from 2.43% to 14.06% with 𝑛𝛾 = 8 in our carriers’ profits and underline the importance of choosing a suitable
experiments. For every instance type, the collaboration savings of the acceptance policy. The performance of an acceptance policy depends
Feasible policy are exceeded by those of at least one overbooking policy. on the revenue per request. In general, the slope of the profit curve
For the instances with 𝑛𝛾 = 4, the Close+Easy policy provides the largest is larger for policies with high threshold settings, i.e., that accept more
collaboration savings (marked underlined for each instance type) for requests. However, these policies only outperform the policies with low
both the D10-R20 and the D20-R10 instances. The Easy policy performs threshold settings in some cases. The Close+Easy policy with 𝜖 = 10 km
best for the D20-R20 instances. In the densest D10-R10 instances, obtains the best results for smaller revenues per request. The average
where distance may not be as decisive, the Next policy provides the costs per request using this policy are even smaller than using the
best results. While the instances with 𝑛𝛾 = 8 show similar ranges for Feasible policy. Since the absolute profit is smaller for low settings of
the collaboration savings with a smaller number of offered bundles, revenue per request, this results in a decreasing curve. For the other
the impact of the acceptance policy cannot be determined as clearly policies, overbooking leads to increased average costs per request that
due to the heuristic bundle generation. In general, a small amount of are compensated by the respective revenue, resulting in increasing

623
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Table 3
Collaboration savings for different instance types, number of selected requests, and acceptance policies.
Policy 𝜖 Instance type
D10-R10 D10-R20 D20-R10 D20-R20
𝑛𝛾 = 4 𝑛𝛾 = 8 𝑛𝛾 = 4 𝑛𝛾 = 8 𝑛𝛾 = 4 𝑛𝛾 = 8 𝑛𝛾 = 4 𝑛𝛾 = 8
Feasible 3.95% 2.43% 7.23% 7.52% 3.57% 4.25% 4.57% 3.17%
Next 1 7.37% 5.16% 9.48% 10.36% 4.41% 5.26% 6.59% 4.95%
2 8.51% 6.45% 8.83% 10.48% 4.32% 5.48% 6.11% 5.06%
3 8.38% 6.78% 6.68% 11.09% 4.53% 6.53% 4.93% 6.29%
4 4.74% 7.48% 2.58% 12.26% 1.61% 6.63% 1.52% 7.87%
Easy 2.5 km 4.98% 3.52% 8.66% 9.14% 3.28% 5.22% 5.86% 3.75%
5.0 km 7.96% 6.34% 9.40% 11.00% 3.73% 6.24% 7.06% 5.74%
7.5 km 8.24% 8.31% 10.74% 13.78% 3.82% 6.71% 8.16% 8.53%
Close 2.5 km 7.74% 4.83% 9.32% 11.93% 3.55% 6.23% 7.09% 5.64%
5.0 km 6.41% 7.14% 3.59% 8.98% 3.43% 6.58% 4.53% 8.16%
7.5 km 5.07% 5.36% 2.71% 4.66% 2.03% 6.20% 1.74% 4.88%
Close+Easy 10 km 7.56% 6.10% 9.62% 10.73% 4.68% 6.59% 5.39% 3.98%
15 km 6.53% 7.51% 10.78% 14.06% 3.10% 6.36% 7.85% 6.95%
20 km 4.74% 4.79% 4.91% 11.79% 1.61% 4.68% 5.28% 10.66%

Fig. 8. Impact on profit for all acceptance policies with overbooking compared to Feasible policy on D10-R20 instances.

curves. Based on the results of the Easy policy, it can be observed that beneficial to accept requests with larger distances to depots. This can be
the threshold setting can be adapted to different revenues per request noted by the line of 𝜖 = 15 km not intersecting with that of 𝜖 = 10 km in
to enhance profit gains. The Next policy and the Close policy with the the considered revenue window. In the instances with smaller service
smallest threshold setting can still achieve minor profit gains for high areas, the impact of overbooking is smaller. While relatively small
revenues per request, but they cannot match the performance of the profit gains can still be achieved in the D10-R10 instances (Fig. 9(a)),
other policies with suitable threshold settings. this is even more difficult in the D20-R10 instances (Fig. 9(c)) where
Overall, the results also show that overbooking can have a substan- only little collaboration is possible (see Table 3).
tial negative impact on the overall profit if the wrong acceptance policy
is chosen. High profit losses may be suffered in particular with small Asymmetric settings. Finally, we aim to assess the incentive for a carrier
revenues per request and thresholds set too large. Even with a revenue to deviate from a symmetric setting in which all carriers follow the
per request of 50 – which equals the penalty costs for outsourcing – same acceptance policy. For this reason, we evaluate the impact on
some overbooking policies perform worse than the Feasible policy. This profit if either (1) a single carrier uses an overbooking policy with
is due to lost collaboration savings in cases with a high number of the other two carriers using the Feasible policy (deviating from no-
overbooked requests (see Tables 2 and 3) that result from carriers not overbooking strategy), or (2) two carriers use the same overbooking
being able to bid values lower than the penalty cost once their route policy with the other carrier using the Feasible policy (deviating from
capacities are exhausted even after the request selection. overbooking strategy). In the results reported in Fig. 10, we again focus
In Fig. 9, we analyze the performance of the Close+Easy policy in on the Close+Easy policy with its three settings of threshold 𝜖 and the
more detail. The results for all four instance types are presented, while D10-R20 instances. This combination has shown to provide both the
the three threshold settings 𝜖 = {10, 15, 20} km are depicted in different largest profit gains and the highest sensitivity to the threshold in the
shades, respectively. The impact on profit and the differences between symmetric setting. The lines previously shown in Fig. 9(b) correspond
the threshold settings are particularly distinct with instance type D10- to the dashed lines in Figs. 10(a) to 10(f), with their shade denoting
R20 as it provides the largest overlap (Fig. 9(b)). If the carriers’ depots the respective threshold setting. In the symmetric setting, the threshold
are located further away, as in the D20-R20 instances (Fig. 9(d)), it is setting 𝜖 = 10 km yields profit gains compared to the Feasible policy

624
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 9. Impact on profit of Close+Easy with 𝜖 = 10 km (light), 𝜖 = 15 km (medium), and 𝜖 = 20 km (dark) compared to Feasible for different instance types.

for all evaluated revenues per request if it is applied by all carriers 8. Conclusions and future research
(Figs. 10(a), 10(b)), while 𝜖 = 15 km does so only for higher revenues
per request (Figs. 10(c), 10(d)) and 𝜖 = 20 km is not profitable at all In conclusion, this work considers a stochastic, dynamic, and col-
(Figs. 10(e), 10(f)). laborative problem setting of a carrier comprising multiple types of
Regarding the asymmetric settings, we depict in the left column decisions. In a primary market phase, stochastic customer requests
(Figs. 10(a), 10(c), 10(e)) the results for one overbooking carrier and in are dynamically accepted. In a secondary market phase, requests are
the right column (Figs. 10(b), 10(d), 10(f)) those for two overbooking selected and bids for bundles are generated in a combinatorial auction
carriers. Solid lines depict the impact on profit for the overbooking with other carriers. The implications on the final fulfillment using
carrier(s) using the Close+Easy policy with the respective threshold vehicle routes must be considered in every decision. We propose an in-
setting compared to applying the Feasible policy. Dotted lines depict the tegrated modeling approach that allows to investigate how the options
impact on profit for the other carrier(s) sticking to the Feasible policy. provided by a secondary market, organized as a combinatorial auction,
affect carrier decisions concerning the primary market interacting with
In general, it can be observed that overbooking in an asymmetric
customers. The carriers’ sequential optimization problem is modeled as
setting is not a profitable strategy. While it can provide profit gains
a Markov decision process. We develop heuristic policies for solving the
above a certain revenue per request, carriers not performing overbook-
problem that take into account the options provided by the secondary
ing are better off on average. This is likely due to the risk of paying high
market during the primary market phase. Numerical experiments are
penalty fees if overbooked requests cannot be traded, which also makes
conducted to provide insights into the interaction of the primary and
the overbooking carrier less competitive in the bidding stage. Moreover,
the secondary market and to study the value for carriers to consider
it can also be concluded that deviating from successful symmetric
them in an integrated problem.
overbooking strategies, such as Close+Easy with 𝜖 = 10 km, is not
The experimental results show that carriers in this setting can
profitable above a certain revenue per request. It can be, however, for achieve considerable collaboration gains by trading only a relatively
unsuccessful strategies, e.g., with 𝜖 = 20 km because it reduces the total small number of requests in a combinatorial auction with other car-
number of overbooked requests. riers. These collaboration savings directly correspond to a reduction
Overall, these findings underline the importance of identifying a of the vehicles’ overall driving distance and, thus, imply an impact in
suitable acceptance policy that can be applied by carriers to ensure terms of reducing congestion and emissions. We also notice that the
a stable collaboration. With the distinction between carriers in this collaboration savings are not as high as in some experiments in previous
asymmetric setting, the individual auction payments, that are impacted literature that consider static problem settings and primarily focus on
by the egalitarian profit sharing mechanism, also play a role. Profit the secondary market. This is likely due to the nature of our specific
sharing mechanisms that recognize the individual contribution of each problem, in which all carriers accept requests up to a point where their
carrier, such as the one proposed in Gansterer, Hartl and Sörensen fleet capacity is highly utilized. Therefore, it is important to recognize
(2020), may be able to counteract the observed effect. the revenue-generating aspect of the request acceptance decisions.

625
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. 10. Impact on profit for asymmetric settings (left figures: one overbooking carrier; right figures: two overbooking carriers) compared to symmetric settings using the Close+Easy
policy with different thresholds 𝜖 on D10-R20 instances.

Our study finds that the right extent of overbooking, i.e., accept- to consider the flexible reassignment of requests among planned routes
ing a few additional requests that are attractive to other carriers, and the outsourcing set. Anticipatory policies could be designed or
can contribute to increased overall profits. The overall collaboration learned that, e.g., consider strategically rejecting requests in anticipa-
savings provided by a combinatorial auction can be even larger with
tion of more promising future requests. This is particularly challenging
overbooking than without overbooking. Also, it can be concluded that
overbooking is most profitable if conducted by all collaborating car- in applications, in which the requests of some customers are more
riers in a symmetric way. In most asymmetric cases, deviations of a important or even not rejectable. Furthermore, the effect of strategic
single carrier are not beneficial due to the high risk of paying penalty behavior in any of the carriers’ decisions should be evaluated over
fees if overbooked requests cannot be traded. These numerical results multiple periods. Decision-making may be further improved by incorpo-
could indicate that an equilibrium for the extent of overbooking is not
rating predictions of the auction outcome, gained, e.g., using Machine
strongly affected by a prisoner’s dilemma situation.
Perspectives for future research lie in improving the proposed poli- Learning techniques. Finally, the design of efficient auction mecha-
cies, e.g., by including a parameter tuning approach, and developing nisms that allow for tackling larger instances and recognize strategic
more sophisticated policies for solving this problem. This may include behavior of carriers should be further investigated.

626
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Acknowledgments 𝑇𝑖𝑚 ≥ 0 ∀𝑖 ∈ , 𝑚 ∈ 𝑀,
(A.14)
This research was funded by the Austrian Science Fund (FWF,
𝑄𝑖𝑚 ≥ 0 ∀𝑖 ∈ , 𝑚 ∈ 𝑀. (A.15)
project P 34502).
The objective function (A.1) minimizes the total costs from routing
Appendix A. Routing problem
and outsourcing. Constraints (A.2) enforce that each request is served
exactly once or it is outsourced. Constraints (A.3) define that the pickup
Based on typical vehicle routing formulations, we introduce the
node and the delivery node of a request are visited by the same vehicle.
following notation. A complete graph  = (, ) is given. The set of
It is guaranteed that all routes start at the origin depot node due to
nodes  =  ∪  ∪  consists of pickup nodes , delivery nodes , and
depot nodes  = {0, 2𝑛 + 1}. Pickup nodes  = {1, … , 𝑛} and delivery Constraints (A.4), follow Constraints (A.5) that ensure connectivity, and
nodes  = {𝑛 + 1, … , 2𝑛} are created for the number of customer end at the destination depot node due to Constraints (A.6). Consistency
requests 𝑛 = |𝐶𝑘 |. The loads and service times of the requests 𝑐 ∈ 𝐶𝑘 are of the time and load variables is determined using Constraints (A.7) and
assigned to the associated nodes 𝑖 ∈ . The load 𝑞𝑖 for a pickup node (A.8), respectively. Note that these constraints are written in this simple
𝑖 ∈  is based on the request’s load 𝑞𝑐 , with the load of the respective version for illustration purposes and should at best be implemented
delivery node 𝑛 + 𝑖 ∈  being negative, i.e., 𝑞𝑛+𝑖 = −𝑞𝑖 . There is no in a linear way. Constraints (A.9) are the precedence constraints for
load at the depot with 𝑞0 = 𝑞2𝑛+1 = 0. The service times 𝑠𝑖 = 𝑠𝑛+1 at the pickup and delivery nodes of a request. Constraints (A.10) limit
pickup nodes 𝑖 ∈  and delivery nodes 𝑛 + 𝑖 ∈  are equally based the duration of each route, while Constraints (A.11) ensure the load
on the request’s service time 𝑠𝑐 . There is no service time at the depot capacity restriction of each vehicle. Finally, the binary variables for
with 𝑠0 = 𝑠2𝑛+1 = 0. The set of arcs is defined as  = {(𝑖, 𝑗) ∶ 𝑖, 𝑗 ∈ } routing and outsourcing are defined in (A.12) and (A.13), respectively,
with 𝑖 ≠ 2𝑛 + 1, 𝑗 ≠ 0, 𝑖 ≠ 𝑗, 𝑖 ≠ 𝑗 + 𝑛. Associated with each arc (𝑖, 𝑗) is a while the continuous time and load variables are defined in (A.14) and
travel time 𝑡𝑖𝑗 . The set of vehicles 𝑀 is considered, with each of their (A.15), respectively.
routes being restricted to a maximum duration 𝐿 and a load capacity The values of the decision variables in a solution to this routing sub-
𝐶. To enforce those restrictions, 𝑇𝑖𝑚 denotes the time at which vehicle problem can be transferred to a preliminary route plan and outsourcing
𝑚 begins service at node 𝑖 and 𝑄𝑖𝑚 denotes the load of vehicle 𝑚 after set in a decision point 𝑘 of the MDP. The route plan 𝜃𝑘 can be obtained
visiting node 𝑖.
from variables 𝑥𝑖𝑗𝑚 with positive solution values and the outsourcing
Two types of binary decision variables are considered. Variables
set 𝐶𝑘𝑜 includes those requests for which the respective variable 𝑦𝑖 has
𝑥𝑖𝑗𝑚 ∈ {0, 1} indicate for each vehicle 𝑚 whether it travels from node
a positive solution value.
𝑖 to node 𝑗, which is associated with the respective routing costs 𝑐𝑖𝑗 .
Variables 𝑦𝑖 ∈ {0, 1} indicate outsourcing of a request with pickup node
𝑖 that cannot be feasibly served in any of the routes. Outsourcing is Appendix B. Profit sharing analysis
associated with a – typically high – penalty fee 𝑓𝑖 . The overall objective
is to minimize the total costs for routing and for outsourcing such that
In this section, we give insights on the value of the profit sharing
all pickup and delivery requests are fulfilled.
mechanism based on an analysis of the experimental results on a per-
We depict the routing problem using the mixed integer linear
program (A.1)–(A.15). instance, per-carrier basis. In the following, we summarize the absolute
∑∑ ∑ ∑ collaboration savings per carrier, i.e., the difference between the fulfill-
𝑧 = min 𝑐𝑖𝑗 𝑥𝑖𝑗𝑚 + 𝑓𝑖 𝑦𝑖 (A.1) ment costs before and after the redistribution, in a scenario without
𝑖∈ 𝑗∈ 𝑚∈𝑀 𝑖∈
any profit sharing compared to with our profit sharing mechanism.
subject to Fig. B.11 shows results for all instance types if all carriers use the
∑ ∑ Feasible policy B.11(a), the Close+Easy policy with 𝜖 = 10 km as a
𝑥𝑖𝑗𝑚 + 𝑦𝑖 = 1 ∀𝑖 ∈ , (A.2)
𝑗∈ 𝑚∈𝑀
successful overbooking policy B.11(b), and the Close+Easy policy with
∑ ∑ 𝜖 = 20 km as a less successful one B.11(c). Following the notation
𝑥𝑖𝑗𝑚 − 𝑥𝑛+𝑖,𝑗𝑚 = 0 ∀𝑖 ∈ , 𝑚 ∈ 𝑀, (A.3)
introduced in Section 4, the light bars denote the savings 𝛽𝛾 − 𝛼𝛾 of
𝑗∈ 𝑗∈
∑ a carrier 𝛾 ∈ 𝛤 before profit sharing, while the dark bars denote the
𝑥0𝑗𝑚 = 1 ∀𝑚 ∈ 𝑀, (A.4) savings 𝛽𝛾 − 𝛼𝛾 + 𝜓𝛾 after profit sharing.
𝑗∈
∑ ∑ As the auction is assumed to be budget-balanced, i.e., the auctioneer
𝑥𝑗𝑖𝑚 − 𝑥𝑖𝑗𝑚 = 0 ∀𝑖 ∈  ∪ , 𝑚 ∈ 𝑀, (A.5) does not provide or charge payments that would exceed the auction
𝑗∈ 𝑗∈
∑ profits, the mean values before profit sharing and after profit sharing
𝑥𝑖,2𝑛+1,𝑚 = 1 ∀𝑚 ∈ 𝑀, (A.6) would be equivalent for every instance type. The impact of the profit
𝑖∈
sharing mechanism can in all settings be noticed clearly, however, in
the variance of the values. This is depicted by the box plots showing
𝑥𝑖𝑗𝑚 = 1 ⟹ 𝑇𝑗𝑚 ≥ 𝑇𝑖𝑚 + 𝑠𝑖 + 𝑡𝑖𝑗 ∀𝑖 ∈ , 𝑗 ∈ , 𝑚 ∈ 𝑀,
the minimum, first quartile, median, third quartile, and maximum
(A.7) value, respectively. Note that the collaboration savings may be neg-
𝑥𝑖𝑗𝑚 = 1 ⟹ 𝑄𝑗𝑚 ≥ 𝑄𝑖𝑚 + 𝑞𝑖 ∀𝑖 ∈ , 𝑗 ∈ , 𝑚 ∈ 𝑀, ative, i.e., an individual carrier would be worse off in an instance,
(A.8) before applying the profit sharing. This can particularly be observed in
unsuccessful overbooking settings where the redistribution of requests
𝑇𝑛+𝑖,𝑚 − 𝑇𝑖𝑚 − 𝑠𝑖 − 𝑡𝑖,𝑛+𝑖 ≥ 0 ∀𝑖 ∈ , 𝑚 ∈ 𝑀, (A.9)
is more difficult and a carrier may even win requests that cannot
𝑇2𝑛+1,𝑚 − 𝑇0𝑚 ≤ 𝐿 ∀𝑚 ∈ 𝑀, (A.10) be fulfilled. After applying the profit sharing, all carriers have an
max{0, 𝑞𝑖 } ≤ 𝑄𝑖𝑚 ≤ min{𝐶, 𝐶 + 𝑞𝑖 } ∀𝑖 ∈ , 𝑚 ∈ 𝑀, equal outcome resulting from the auction, which is why the remaining
(A.11) variance only depicts the differences between individual instances, that
may have different total auction profits. No more negative collabora-
𝑥𝑖𝑗𝑚 ∈ {0, 1} ∀𝑖 ∈ , 𝑗 ∈ , 𝑚 ∈ 𝑀,
tion savings, i.e., individual losses, can be observed in any instance.
(A.12)
This must be ensured such that carriers always have an incentive for
𝑦𝑖 ∈ {0, 1} ∀𝑖 ∈ , (A.13) participating in the collaboration (individual rationality).

627
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Fig. B.11. Collaboration savings per carrier (box plots with minimum, first quartile, median, third quartile, maximum) before profit sharing (light) and after profit sharing (dark)
for different instance types.

References Gansterer, M., & Hartl, R. F. (2016). Request evaluation strategies for carriers in
auction-based collaborations. OR Spectrum, 38(1), 3–23.
Abrache, J., Crainic, T. G., Gendreau, M., & Rekik, M. (2007). Combinatorial auctions. Gansterer, M., & Hartl, R. F. (2018a). Centralized bundle generation in auction-based
Annals of Operations Research, 153(1), 131–164. collaborative transportation. OR Spectrum, 40(3), 613–635.
Agatz, N., Hewitt, M., & Thomas, B. W. (2020). ‘‘Make no little plans’’: Impactful Gansterer, M., & Hartl, R. F. (2018b). Collaborative vehicle routing: A survey. European
research to solve the next generation of transportation problems. Networks, 77(2), Journal of Operational Research, 268(1), 1–12.
Gansterer, M., Hartl, R. F., & Savelsbergh, M. (2020). The value of information in
269–286.
auction-based carrier collaborations. International Journal of Production Economics,
Archetti, C., Speranza, M. G., & Vigo, D. (2014). Chapter 10: Vehicle routing problems
221, Article 107485.
with profits. In P. Toth, & D. Vigo (Eds.), Vehicle routing (pp. 273–297). Society
Gansterer, M., Hartl, R. F., & Sörensen, K. (2020). Pushing frontiers in auction-based
for Industrial and Applied Mathematics.
transport collaborations. Omega, 94, Article 102042.
Ausseil, R., Pazour, J. A., & Ulmer, M. W. (2022). Supplier menus for dynamic matching
Gansterer, M., Hartl, R. F., & Tzur, M. (2022). Transportation in the sharing economy.
in peer-to-peer transportation platforms. Transportation Science, 56(5), 1304–1326.
Transportation Science, 56(3), 567–570.
Battarra, M., Cordeau, J.-F., & Iori, M. (2014). Chapter 6: Pickup-and-delivery problems
Gansterer, M., Hartl, R. F., & Vetschera, R. (2018). The cost of incentive compatibility
for goods transportation. In P. Toth, & D. Vigo (Eds.), Vehicle routing (pp. 161–191).
in auction-based mechanisms for carrier collaboration. Networks, 73(4), 490–514.
Society for Industrial and Applied Mathematics.
Goodson, J. C., Thomas, B. W., & Ohlmann, J. W. (2017). A rollout algorithm
Bellman, R. (1957). A Markovian decision process. Journal of Mathematics and
framework for heuristic solutions to finite-horizon stochastic dynamic programs.
Mechanics, 6(5), 679–684.
European Journal of Operational Research, 258(1), 216–229.
Berbeglia, G., Cordeau, J.-F., & Laporte, G. (2010). Dynamic pickup and delivery Guajardo, M., & Rönnqvist, M. (2016). A review on cost allocation methods in col-
problems. European Journal of Operational Research, 202(1), 8–15. laborative transportation. International Transactions in Operational Research, 23(3),
Berger, S., & Bierwirth, C. (2010). Solutions to the request reassignment problem 371–392.
in collaborative carrier networks. Transportation Research Part E: Logistics and Guo, Y., Yu, J., Allaoui, H., & Choudhary, A. (2022). Lateral collaboration with
Transportation Review, 46(5), 627–638. cost-sharing in sustainable supply chain optimisation: A combinatorial framework.
Chu, C.-W. (2005). A heuristic algorithm for the truckload and less-than-truckload Transportation Research Part E: Logistics and Transportation Review, 157, Article
problem. European Journal of Operational Research, 165(3), 657–667. 102593.
Cleophas, C., Cottrill, C., Ehmke, J. F., & Tierney, K. (2019). Collaborative urban trans- Klapp, M. A., Erera, A. L., & Toriello, A. (2020). Request acceptance in same-day
portation: Recent advances in theory and practice. European Journal of Operational delivery. Transportation Research Part E: Logistics and Transportation Review, 143,
Research, 273(3), 801–816. Article 102083.
Cruijssen, F., Cools, M., & Dullaert, W. (2007). Horizontal cooperation in logis- Krajewska, M. A., & Kopfer, H. (2006). Collaborating freight forwarding enterprises.
tics: Opportunities and impediments. Transportation Research Part E: Logistics and OR Spectrum, 28(3), 301–317.
Transportation Review, 43(2), 129–142. Li, Y., Chen, H., & Prins, C. (2016). Adaptive large neighborhood search for the pickup
de Vries, S., & Vohra, R. V. (2003). Combinatorial auctions: A survey. INFORMS Journal and delivery problem with time windows, profits, and reserved requests. European
on Computing, 15(3), 284–309. Journal of Operational Research, 252(1), 27–38.
Ehmke, J. F., & Campbell, A. M. (2014). Customer acceptance mechanisms for home Los, J., Schulte, F., Gansterer, M., Hartl, R. F., Spaan, M. T. J., & Negenborn, R.
deliveries in metropolitan areas. European Journal of Operational Research, 233(1), R. (2022). Large-scale collaborative vehicle routing. Annals of Operations Research,
193–207. [Link] Available online.
Ferrell, W., Ellis, K., Kaminsky, P., & Rainwater, C. (2019). Horizontal collaboration: Los, J., Schulte, F., Spaan, M. T., & Negenborn, R. R. (2020). The value of information
opportunities for improved logistics planning. International Journal of Production sharing for platform-based collaborative vehicle routing. Transportation Research
Research, 58(14), 4267–4284. Part E: Logistics and Transportation Review, 141, Article 102011.

628
Y.O. Scherr et al. European Journal of Operational Research 314 (2024) 612–629

Montoya-Torres, J. R., Muñoz-Villamizar, A., & Vega-Mejía, C. A. (2016). On the impact Rüther, C., & Rieck, J. (2022). Bundle selection approaches for collaborative practical-
of collaborative strategies for goods delivery in city logistics. Production Planning oriented pickup and delivery problems. EURO Journal on Transportation and
and Control, 27(6), 443–455. Logistics, 11, Article 100087.
Pan, S., Trentesaux, D., Ballot, E., & Huang, G. Q. (2019). Horizontal collaborative Savelsbergh, M. W. P., & Sol, M. (1995). The general pickup and delivery problem.
transport: survey of solutions and practical implementation issues. International Transportation Science, 29(1), 17–29.
Journal of Production Research, 57(15–16), 5340–5361. Schopka, K., & Kopfer, H. (2017). Pre-selection strategies for the collaborative vehicle
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery routing problem with time windows. In H. Freitag, & J. Pannek (Eds.), Lecture
problems. Journal für Betriebswirtschaft, 58(2), 81–117. notes in logistics, Dynamics in logistics (pp. 231–242). Cham: Springer International
Pekeč, A., & Rothkopf, M. H. (2003). Combinatorial auction design. Management Science, Publishing.
49(11), 1485–1503. Soeffker, N., Ulmer, M. W., & Mattfeld, D. C. (2022). Stochastic dynamic vehicle routing
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic in the light of prescriptive analytics: A review. European Journal of Operational
vehicle routing problems. European Journal of Operational Research, 225(1), 1–11. Research, 298(3), 801–820.
Powell, W. B. (2011). Approximate dynamic programming. John Wiley & Sons, Inc. Speranza, M. G. (2018). Trends in transportation and logistics. European Journal of
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic Operational Research, 264(3), 830–836.
programming. Wiley. Ulmer, M. W., Goodson, J. C., Mattfeld, D. C., & Thomas, B. W. (2020). On modeling
Rios, B. H. O., Xavier, E. C., Miyazawa, F. K., Amorim, P., Curcio, E., & Santos, M. J. stochastic dynamic vehicle routing problems. EURO Journal on Transportation and
(2021). Recent dynamic vehicle routing problems: A survey. Computers & Industrial Logistics, 9(2), Article 100008.
Engineering, 160, Article 107604. van Heeswijk, W. J. A., Mes, M. R. K., & Schutten, J. M. J. (2019). The delivery dis-
Ritzinger, U., Puchinger, J., & Hartl, R. F. (2016). A survey on dynamic and patching problem with time windows for urban consolidation centers. Transportation
stochastic vehicle routing problems. International Journal of Production Research, Science, 53(1), 203–221.
54(1), 215–231. Wang, X., & Kopfer, H. (2015). Rolling horizon planning for a dynamic collaborative
routing problem with full-truckload pickup and delivery requests. Flexible Services
and Manufacturing Journal, 27(4), 509–533.

629