Freight on Transport problem: Extended formulation and column
generation approach
C. Archettia,∗ , D. Delle Donnea and A. Santinia,b,c
a <ESSEC Business School>, <Paris>, <Frrance>
archetti@essec.edu, delledonne@essec.edu, santini@essec.edu
b <Institute for Advanced Studies, Paris Cergy Université>, <Cergy>, <France>c <Department of Economics & Business, Universitat Pompeu Fabra>, <Barcelona>, <Spain>∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
March 18, 2022Keywords: (e-commerce; last-mile delivery; Freight on Transport; column generation)

1

INTRODUCTION

The last-mile delivery is the most expensive part of the whole freight delivery process, in addition to being the most unsustainable one. The delivery system aects not only the shipping
companies, but urban life as well. There are several stakeholders in the last-mile delivery system,
either direct or indirect, who are impacted. The impact caused by vehicles performing deliveries
associated with last-mile operations can be three-fold: economic, social and environmental (ViuRoig & Alvarez-Palau, 2020). To keep up with the growing demands and resulting issues causedby e-commerce delivery systems, companies are looking towards innovative approaches that reduces the costs of social and environmental externalities. In this work we consider the strategy
based on the use of Public Transport Services for delivery operations. The eectiveness of an
integrated delivery system on public transit has already been demonstrated in several cities (seeMarinov et al. (2013), Saito (2021), Cleophas et al. (2019)). Amazon is also looking towards
using public buses for its deliveries, and has received a patent that would transform buses intoparcel carriers (Baron, 2019, Reul, 2019).
In this paper, we study a problem which we call as the Operational Freight on Public Transport (OpFOT hereafter) problem. It consists of a three-tier package delivery system. In therst tier (also referred as T1), the packages are delivered from the Consolidation and Distribution Center (CDC) to nearby stops of the public transportation vehicles from which they canbe picked up by these vehicles. We call these stops drop-in stops. The second tier (T2) of thedelivery is the one that occurs on-board public vehicles, which have pre-determined schedules,
itineraries and stops. The vehicles pick the packages from the drop-in stops and transport themto some other stops on their routes, which we call drop-out stops. The stops where the packages
are dropped by the vehicles are within the city and are close to the customer locations. Finally,
the city freighters pick the packages from the drop-out stops and deliver them to their respective
customers, using sustainable and green modes of transport, like electric vehicles, drones, bikes,or even freighters simply walking for the delivery. This constitutes the third and nal tier ofthe problem (T3). The goal is to determine the routes in T1 and T3 such that the corresponding cost is minimized. To the best of our knowledge, we are the rst to study this three-layer
Freight-on-Transport delivery system.
TRISTAN XI Symposium

Original abstract submittal

C. Archetti, D. Delle Donne and A. Santini22 Problem denition
The OpFOT problem was introduced in Mandal & Archetti (2021) and is formally described asfollows.
A set C of customers is dened where each customer c ∈ C requests the delivery of one parcelof size qc ≥ 0 during a delivery time window [Tce , Tcl ] at a location of her/his choice. We assume
that all delivery requests are known in advance and that all parcels start their journey at aConsolidation and Distribution Centre (CDC), denoted with o.
In the rst tier, parcels are moved from the CDC to public transport stops in the set Sin
through a set D of homogeneous trucks of capacity Qd . Each time a truck moves from a locationi to a location j , it incurs a cost cij which is proportional to the distance between i and j .
In the second tier, each parcel travels between two bus stops, aboard a bus. Specically,parcels are picked up from a bus stop in Sin and delivered to a stop in Sout . We denote the busp|eet as P . Each bus p ∈ P has capacity Qp and serves a route Sp = (s1p , . . . , s|Sp ) represented
by the ordered list of stops the bus visits.
In the third tier, freighters move parcels between bus stops and customer locations. We denotewith K the set of homogeneous freighters with capacity Qf who can perform the deliveries tothe customers. Each freighter k ∈ K is assigned to a stop sk ∈ Sout where she/he can startand end his service. Freighter travel time between locations i, j ∈ Sout ∪ C is denoted as lij .
Each freighter route has a maximum duration of Lmax , which includes both the travel timeand service times Tc incurred when delivering parcels to customers c ∈ C . In addition, as fortrucks in Tier 1, freighters incur a cost cij when moving from a location i to a location j which is
proportional to the distance, but might be dierent than the cost associated with trucks. Indeed,
as freighters typically use light vehicles to perform deliveries (e.g., bikes) the associated travelingcost is typically much smaller than the one related with trucks.
The OpFOT problem asks to design the routes of both delivery trucks and freighters anddetermine which bus should carry each package, in order to deliver every package according tocapacities and time constraints, while minimising the cost of the designed routes. Note that no
cost is associated with Tier 2, i.e., with the use of public transport. This is because buses will
be used anyway for passenger transportation.

3 An extended IP formulation
Let Rd (resp. Rf ) be the set of feasible routes for delivery trucks from the depot to stops (resp.
for freighters from a stop to the customers). Each route r ∈ Rd ∪ Rf , is associated with the setof packages transported by the vehicle, the cost of the route cr as well as the departure time of
the route. We introduce a binary variable xr ∈ {0, 1} for each truck route r ∈ Rd which states
whether route r is part of the solution or not. Analogously, we use a binary variable yr ∈ {0, 1}
for each freighter route r ∈ Rf . To properly model the transport of the parcels by the publicin ∈ {0, 1} to state whether bus p ∈ P picks up the parcel
buses, we employ binary variables zpcs
out ∈ {0, 1} which states whether bus p ∈ Pof customer c ∈ C at stop s ∈ Sin , and variables zpcs
drops the parcel of customer c ∈ C at stop s ∈ Sout . In the following, we will dene as S c asthe stops which can be used to serve customer c ∈ C and Sp as stops served by bus p ∈ P . Ourformulation for OpFOT consists in the minimisation of the costs of the selected routes subject
to several constraints ensuring that: (i) the selected routes on the 3 echelons are compatible, (ii)the resources (e.g., capacities, etc.) on each echelon are not exceeded, and (iii) every customer
receives its parcel on time.
Objective function:

minXr∈RdTRISTAN XI Symposiumcr xr +X

cr yr .

(1)

Rf

Original abstract submittalC. Archetti, D. Delle Donne and A. Santini

3Constraints:

 Maximum number of trucks:
Xxr ≤ |D|.

(2)

yrs ≤ |K|.

(3)

r∈Rd

 Maximum number of freighters:
Xr∈Rfs Each parcel must be moved by one bus:
XX

inzpcs=1cp∈Pc s1 ∈Sp ∩Sin

X

Xoutzpcs= 1 ∀c ∈ C.
2

(4)

cp∈Pc s2 ∈Sp ∩Sout

 A bus either do both pick up and drop o a parcel or none of these:
Xcs1 ∈Sp ∩Sin∀c ∈ C, ∀p ∈ Pc .

(5)∀p ∈ P, ∀i ∈ {1, . . . , |Sp | − 1}.

(6)

Xin
zpcs
=1s2 ∈Spoutzpcs
2∩S cout Bus capacities are respected:
Xc∈CqcX

inoutzpcs
j − zpcsj
pj≤ip

≤ Qp

 Some route must have dropped a parcel which is picked up at an in-station:
Xinzpcs≤1xrc∀c ∈ C, ∀p ∈ Pc , ∀s1 ∈ Sin∩ Sp .

(7)r∈Rdpcs

1

 Some route must be delivering a parcel which is dropped o at an out-station:
outzpcs≤2Xyrc∀c ∈ C, ∀p ∈ Pc , ∀s2 ∈ Sout∩ Sp(8)r∈Rfpcs

where Rfpcs are all the freighter routes routes delivering package c from stop s, starting at
a time compatible with route r.
We note that the methodology proposed in the following can be adapted to dierent problem setting, like dierent cost functions for vehicles used in the rst and third layer. We also
note that capacity constraints of trucks and freighters are handled in the corresponding pricing
subproblems.
3.1

The pricing subproblems

As the above formulation may have exponentially-many variables, we propose to tackle thesolution of its linear relaxation with a column generation approach. To this end, both sets ofx- and y -variables shall be dynamically generated during the solution process according to thevalues in the current optimal solution of the restricted master problem. The pricing subproblems
associated with x and y variables can be stated as elementary shortest path problems withresource constraints (ESPPRC) in which the cost of visiting a node depends on dierent aspects
which we briey describe in the following.
TRISTAN XI Symposium

Original abstract submittal

C. Archetti, D. Delle Donne and A. Santini

4x. In the case of x variables, i.e., truck routes from the depot dropping
packages at the stops, the cost of visiting a stop s depends both on the packages which are
dropped at s and the time at which the stop is visited. We propose two approaches to solve
this problem: (i) build a graph in which nodes represent pairs (s, c) ∈ S × C and solve a timedependent ESPPRC, and (ii) build a graph in which nodes represent triples (s, c, p) ∈ S × C × Pand solve an ESPPRC problem with time windows.

Pricing variables

y . In the case of y variables, i.e., freighter routes from a stop dropping
packages at nal destinations, the pricing can be solved independently on each potential stop.
From a stop s ∈ S , the cost of visiting a customer c depends on the time at which the routestarts (not on the time the customer is visited). However, the cost function is piece-wise constant.
Based on this fact we partition the time horizon at the points in which this function changes, andsolve one subproblem for each of these time segments restricting the starting time of the routeto the corresponding time interval. Each subproblem is solved as a standard ESPPRC problem
with time windows.
Pricing variables

4 Solution approach
Once the column generation presented above terminates, i.e., it does not nd any new negative
reduced cost column, then the optimal solution of the linear relaxation of the extended formulation is found. We then use the complete set of columns generated to determine a feasible solution
to the OpFOT problem as follows. We build an instance of the extended formulation with the setof columns found and solve the corresponding Mixed-Integer Linear Program (MILP). This procedure is known as restricted master heuristic and widely used in column generation approaches.

5 Computational tests
We tested the approach presented above on the instances proposed in Mandal & Archetti (2021)
and compare it with the problem formulation as well as the three decomposition approaches
presented in this paper. Preliminary tests show that the approach proposed in this paper iscompetitive. However, results highlighted that the pricing problem associated with Tier 1 isextremely cumbersome. Thus, the research is now focused on accelerating this phase and, eventually, nding more eective strategies for the pricing. Also, tests will be made to assess whether
a compact formulation of Tier 1 would be more ecient.

References
Baron, Ethan. 2019. Amazon looks to turn public buses into mobile delivery stations. Accessed 01.10.2021.
Cleophas, Catherine, Cottrill, Caitlin, Ehmke, Jan Fabian, & Tierney, Kevin. 2019. Collaborative urban
transportation: Recent advances in theory and practice. European Journal of Operational Research,273(3), 801816.
Mandal, Minakshi Punam, & Archetti, Claudia. 2021. A decomposition approach to last-mile delivery
using public transportation systems. Technical Report.
Marinov, Marin, Giubilei, Federico, Gerhardt, Mareike, Özkan, Tolgahan, Stergiou, Evgenia, Papadopol,Mihaela, & Cabecinha, Luis. 2013. Urban freight movement by rail. Journal of Transport Literature,7, 87116.
Reul, Maarten. 2019. Amazon to use public transport as parcel carrier. Accessed 01.10.2021.
Saito, Shigeo. 2021. Next stop, package delivery: Bus and courier link up to serve rural area. Accessed
28.09.2021.
Viu-Roig, Marta, & Alvarez-Palau, Eduard J. 2020. The impact of E-Commerce-related last-mile logistics
on cities: A systematic literature review. Sustainability, 12(16), 6492.

TRISTAN XI Symposium

Original abstract submittal