A column generation heuristic for the Pickup and Delivery
Problem with Online Transfers
P.C. Boumana,∗ , G. Özbaygn Tiniçb , L.P. Veelenturfc and R.S.H. Willemsenaa Econometric Institute, Erasmus University, Rotterdam, The Netherlandsbouman@ese.eur.nl, willemsen@ese.eur.nl

b Faculty of Engineering and Natural Sciences, Sabanc University, stanbul, Turkey

ozbaygin@sabanciuniv.edu

c Rotterdam School of Management, Erasmus University, Rotterdam, The Netherlands

lveelenturf@rsm.nl∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
January 15th, 2022

Keywords: Optimization, Vehicle Routing, Shared Mobility, Demand Oriented Transport

1Introduction

Recently there is increasing attention in the literature for more exible and autonomous ways ofpublic transportation. Some focus on semi-exible public transportation. Examples are systems
with a mix of conventional taxis and timetabled shuttle busses (Horn, 2002), limiting the numberof transfers in a transit system with a large number of vehicles (Cortés & Jayakrishnan, 2002),
and integrating xed routes with a general pickup and delivery problem (Aldaihani & Dessouky,2003).
In this research, we focus on full exible passenger transportation. This can be considered asa variant or extension of the Dial-a-Ride Problem (DARP). The focus of the DARP is to bringpassengers from their origin to their destination (e.g. the classical taxi problem). In later variantsof this problem shared door-to-door services were investigated, to see the eect of allowing for
multiple passengers (with dierent origins and destinations) to share the ride. We want to go
one step further and look at the eects of allowing for transfers of passengers in such a shareddoor-to-door service, both online transfers that take place within two driving vehicles that areplatooning, as well as by using outside transfers.
The use of transfers in passenger transportation is not new. In public transport, it is one of
the aspects that is typically considered when making a line plan (Schöbel, 2012). In logistics
delivery services, transferring goods between vehicles at cross-docks or hubs is already quite
common. In courier (pickup and delivery) type of services (Shang & Cu, 1996, Sampaio et al.,2020) we see transfers of passengers. However, these approaches mostly consider transfers at
xed predened locations. In some of these approaches vehicles need to be synchronized, i.e. at
the same location at the same time, to transfer the goods from one delivery vehicle to another,and in other approach this might not be required as temporary storage is allowed so a vehicle
can leave goods for another vehicle to pickup later.
TRISTAN XI Symposium

Original abstract submittal

P.C. Bouman, G. Özbaygn Tiniç, L.P. Veelenturf and R.S.H. Willemsen

2In order to investigate the potential of online transfers (i.e. while moving) in shared door-todoor services, many modelling tricks commonly used in the Dial-a-Ride Problem break down.
Typically the only information about the road network that is required are distances between
pickup and delivery locations, and in extensions of locations where transfers are possible. Incase of online transfers, the actual topology of the road network is required, as facilitating an
online transfer between two vehicles requires that both vehicles share the same road segment atthe same point in time, even though the previous and next pickup and delivery locations arecompletely distinct. While many models for the Dial-a-Ride Problem focus on the sequence ofthe pickups and deliveries of the customers, online transfers require an integrated approach thattakes the exact routes, timing included, of both passengers and vehicles into account.
In our research, we consider a Mixed Integer Program (MIP) to solve this problem, that caneither be solved directly for small instances, or provide the basis for a heuristic in medium
sized instances. We also develop a related column generation approach, and perform extensive
computational experiments. Finally, we provide a number of analytical insights into the possible
advantage of allowing online transfers, but these are omitted from this extended abstract forreasons of brevity.
As far as we know, only Fu & Chow (2022) investigated a closely related problem, the Pickupand Delivery Problem with Synchronized En-Route Transfers. An ecient heuristic is proposed,
as well as a MIP model. However, as opposed to our model this model works with a single typeof transfers, which have to be performed on nodes, ensuring enough time is scheduled to allow
a transfer, while our model supports both online transfers that can take on arcs and outsidetransfers that take place on nodes (but require that the vehicles stop). Furthermore, our model
is dierent since we employ a time-expanded network, rather than Tucker-Miller-Zemlin stylesubtour elimination constraints.

2Methodology

We use a MIP formulation based on a time-expanded network, where a considered time window
is discretized into time units. We assume that demand has strict time windows in which thedemand must either be served or rejected at the cost of a penalty. The formulation can beregarded as a multi-commodity ow where ows associated with the demand consume capacity,whereas the ow associated with the vehicles provides capacity. To enforce that passengers cantransfer in practice, and are not able to transfer when two vehicles cross paths on a node without
forming a platoon, we work with consecutive arc constraints to force that vehicles are platooning
while online transfers take place. Similarly, we use consecutive arc constraints to enforce thatvehicles stop at a node to ensure that a passenger can enter or exit the vehicle. These approaches
do assume that these actions can be performed in one time unit, which requires that the time
discretization works with large enough time units.
The column generation approach we developed works by decomposing paths of vehicles andpassengers out of the MIP model. The columns can be generated by dynamic programming,
which boils down a shortest path algorithm where you need to track the previous arc to deal
with the duals of the consecutive arc constraints. Unfortunately, the column generation seems
to suer from symmetry and/or degeneracy. With stabilization techniques and employing it asa heuristic with a time limit, we are still able to outperform the direct formulation in a numberof medium sized instances, but for smaller instances the direct formulation seems the preferredchoice for many instances.
TRISTAN XI Symposium

Original abstract submittal

P.C. Bouman, G. Özbaygn Tiniç, L.P. Veelenturf and R.S.H. Willemsen

33Experiments and Results

We perform extensive computational experiments. Since many common datasets for DARP only
provide a distance matrix, but do not provide the topology of the road network, we used animplementation of a model proposed by Courtat et al. (2011) to generate ten road networks of
8, 10, 12, 15 and 20 road segments. We generate a set of smaller instances with the following
pairs of numbers of passengers and vehicles: (5, 2), (10, 2), (15, 3), (20, 3) or (40, 6). The vehicles
have 4 seats each. Furthermore, we have a set of larger instances with either 50 or 60 passengers
which have to be served by either 8, 10, 12 or 14 vehicles. We use these instances to compare
the objective value of solving the MIP model with a time limit against solving the heuristic. Weobserve that for the smaller instances, sometimes the MIP approach is better and sometimes thecolumn generation works better, but for the larger instances, the column generation approach
performs better in almost all cases. This comparison is visualized in Figure 1.
We then look at instances where many online transfers are used, to see how the service is designed
by our method. Figure 2 contains a visualization of one example solution that makes extensive
use of online transfers. In Figure 2b it is interesting to observe that there seem to be two main
phases in which the bulk of the passengers are transported. For the majority of passengers, they
are travelling either in the rst half of the second half of the gure. However, four passengers
that make an online transfer from the blue to the yellow vehicle seem to link these phases. It is
our aim to investigate the solution in more detail. Additionally, we also provide some analyticalinsights that tell us in which cases online transfers can be benecial.

4Conclusion

We introduce a MIP model and a column generation model for the Pickup-and-Delivery Problem
with Online Transfers. We have performed a large number of computational experiments withsmall and medium sized instances, where we indeed see online transfers occuring. We intend
to investigate the benets and potential of online transfers in more depth using the developed
methodology.

References
Aldaihani, M., & Dessouky, M. M. 2003. Hybrid scheduling methods for paratransit operations. Computers & Industrial Engineering, 1(1), 7596.
Cortés, Cristián E., & Jayakrishnan, R. 2002. Design and Operational Concepts of High-Coverage Pointto-Point Transit System. Transportation Research Record: Journal of the Transportation Research
Board, 1783(1), 178187.
Courtat, Thomas, Gloaguen, Catherine, & Douady, Stephane. 2011. Mathematics and Morphogenesis ofthe City: A Geometrical Approach. Physical Review E, 83.
Fu, Zhexi, & Chow, Joseph YJ. 2022. The pickup and delivery problem with synchronized en-routetransfers for microtransit planning. Transportation Research Part E: Logistics and Transportation
Review, 157, 102562.
Horn, M. E. T. 2002. Fleet scheduling and dispatching for demand-responsive passenger services. Transportation Research Part C: Emerging Technologies, 10(1), 3563.
Sampaio, A.H., Savelsbergh, Martin W.P., Veelenturf, L.P., & van Woensel, T. 2020. Delivery systems
with crowd-sourced drivers: A pickup and delivery problem with transfers. Networks, 76(2), 232255.
Schöbel, Anita. 2012. Line planning in public transportation: models and methods. OR spectrum, 34(3),491510.
Shang, J. S., & Cu, C. K. 1996. Multicriteria pickup and delivery problem with transfer opportunity.
Computers & Industrial Engineering, 30(4), 631645.

TRISTAN XI Symposium

Original abstract submittal

P.C. Bouman, G. Özbaygn Tiniç, L.P. Veelenturf and R.S.H. Willemsen

4

mip-2h3000
2000

vehicles
236

1000
001000
30m

2000

01000
1h

2000

01000
2000
rootnode-pairs2h(a) Comparison for the smaller instances.
5000
mip-2h4000
vehicles
81012143000
2000
1000
002000
30m

4000

02000
1h

4000 020002h

4000(b) Comparison for the larger instances.

Figure 1  Comparison of a column generation heuristic against solving a MIP model directly.

The MIP has a time limit of two hours, the column generation procedure is stopped either after
thirty, sixty or hundred twenty minutes. Each point represents an instance that was solved, andthe (minimized) objective for dierent methods is reported. Points above the diagonal indicate
the column generation heuristic nds better solutions than the MIP.

(b) Visualization of vehicle occupancy by pas-(a) Visualization of the network

sengers

Figure 2  Example instance and a found solution that services all passengers by utilizing alarge number of online transfers. In Figure 2a, the thin dashed lines connect the origin anddestination of circle-shaped passengers. The thick lines indicate road segments where stopping is
not possible, the thin lines are road segments where stopping at nodes is possible. In Figure 2beach row indicates a passenger and the x-axis indicates time. The colored parts indicate at
which intervals passengers are travelling inside a vehicle, the color indicating the exact vehicle.
Passengers served directly have only a single color in their row, whereas two dierent colors
indicate one online transfer, and three dierent colors indicates two online transfers. A movieof this solution can be accessed via https: // doi. org/ 10. 5281/ zenodo. 5855693.

TRISTAN XI Symposium

Original abstract submittal