Operations Research & City Logistics Planning

Teodor Gabriel Crainic
TeodorGabriel.Crainic@CIRRELT.net

Japan, September 23, 2022

Urban Freight Transport & Logistics
þ “Derived” but essential to most economic and social activitiesñ No transportation = No society as we know it
ñ No logistics = No modern economy
þ Cities cannot survive without freight transportation
ñ Bring in what is needed to live, work & play
ñ Take out what is produced: goods & refuseñ Internal movements of goods for people, stores, firms, institutions, …

2© Crainic 2022

The City and Freight Transportation
Vital but Many Drawbacks

3© Crainic 2022

Issues & Challenges
þ Transportation systems & logistics chains areþ Efficientñ Freight flows around the globe supplying people, industry, institutions
ñ On time, low cost, making a profit …
þ Inefficientñ System perspective: congestion, competing with people, land use, safety, ...
ñ Costs for society, individuals, firms & organizations:environment, energy consumption, time & money lost, ...
ñ Resource – infrastructure, vehicles, facilities - utilization
þ The current model for the development and management of (urban) freighttransportation is not sustainable
4© Crainic 2022

Issues & Challenges (2)þ Heavy trend toward world-wide urbanization

An urban planet of continuously growing cities
þ Accelerating factors
ñ People (and organizations) behaviour & requirements
E-business, Express delivery, JIT/door-to-door, ...
ñ Reverse/green logistics, …
þ Freight volumes, number of vehicles & impacts are continuously growing
þ Better engines but more vehicles Þ
Pollution due to freight transport is raising5© Crainic 2022

What Can We Do? Regulate! Well …
Zoning Access Regulations
Access Forbidden
to Heavy Trucks
HighlyRestrictive
Access& Parking

Necessary
but NOT
Sufficient
sometimes
Detrimental

Regulated parking© Crainic 2022

Serious Freight Traffic Issues in Cities: Nothing New 😇
þ Roma: Imperial city and center of the world (as Rome was claiming ...)
þ Streets shared by people on foot, on horseback, in sedan chairs + chariots

and wagons with iron-clad wheels + vendor stalls + …
ñ Þ Congestion, incidents, accidents …
þ Cesar, 45 a.c., bans cattle-drawn wagons during daylight (except Vestals,
Priests & empties leaving the city)ñ Þ Great noise in the night and unhappy citizens
þ Hadrian,117-138, limits freight traffic during the night as well …
ñ Þ Human (slave)-powered distribution ...
þ ... Larger and larger cities, more and more intensive trade and transport, ...
more and more troubles & regulation with so-and-so results ...
7© Crainic 2022

What Can We Do? Innovate!
þ Change the way things are perceived, planned, and performed
þ “New” organizational (and business) strategies/models
ñ Foster efficient & sustainable transportation & logistics systems

fAddress externalities
fWithout penalizing the economic development
fRally stakeholders and reconcile their requirements
þ Become part of mainstream urban design and planningþ Go beyond “urban freight transport” to City Logistics

8© Crainic 2022

City Logistics
þ Reduce & control freight-vehicle types, flows & impacts
ñ Vehicles (eco-friendly) & infrastructure appropriate for each cityzone/neighbourhood and activity type
ñ Higher capacity utilization, less empty vehicle-kmþ Move from truck-based to a multi/intermodal system
þ To reduce the environmental footprint & impact on congestion & quality oflife (“interference” with people)

9© Crainic 2022

City Logistics (2)þ Continuous developments and challenges
ñ Many projects, ideas, pilot studies, implementations (some) …
ñ For individual organizations or a set of stakeholders

fMany concepts taken up by industry
þ Addressing the demand and the supply sides
ñ Move the freight out of the way in space or timeñ “Optimized” (integrated) logistics system

fCollaboration & sharing (resources, data, & decision making)fConsolidation
fMulti-tier systems
þ Obviously, new technology, new problem settings & decisionsþ ⇒ Challenges for Operations Research & Transportation Science10© Crainic 2022

Single/Last and Two-Tier CL System Settings

External customer zone
OutboundInboundcustomer

Urban-vehicle route
City-freighter route

CDC
Satellite
11© Crainic 2022

Multi-tier Settings

CDC
Satellites(mini hubs, etc.)

12© Crainic 2022

Tier-Appropriate Ecofriendly Vehicles

Frankfurt logistiktram.de - © Herbert Riemann13© Crainic 2022

Multi-tier CL “Classical” vs. Rail (Private) & Transit (Public)

Navigation
City Freighter
Urban Vehicle
Long-Haul Trucks
Rail
Satellite Crossdock
Customer
Distribution center
City Distribution Center
Major flow
City route14© Crainic 2022

Scope of Talk
þ 30+ years of City Logistics
þ ~25 years of Operations Research methodology to plan and manage CL
þ Recall (some) main contributions to planning the supply side of CL
ñ Design the systemñ Design the service
þ With a few thoughts on challenges and perspectives

15© Crainic 2022

Recent Relevant Reviewsþ Marcucci E, Gatta V, Le Pira M (Eds.), Handbook on City Logistics and Urban Freight,

Edward Elgar, 2022 forthcomingñ Crainic, T.G., J. Gonzalez-Feliu, N. Ricciardi, F. Semet, T. Van Woensel,
Operations Research for Planning and Managing City Logistics Systems(long version: CIRRELT-2021-45)
þ Crainic, T.G., G. Perboli, N. Ricciardi,

City Logistics,
Network Design with Applications in Transportation and Logistics, T.G. Crainic, M.
Gendreau, B. Gendron, (Eds.), Springer, 507–537, 2021

16
© Crainic 2022

30 – 25 Years + ...
þ Historically, sporadic interest but for regulation and taxation
þ Brief & intense activity beginning of 70’s: Heavy-vehicle traffic regulation
þ EU and Japan projects in the 90’s

ñ Data surveys ➞ Demand models ...

This field continues to developñ Heavily financed, no real CL business models for long-term activities
f“new” handling activities + extra time & cost need to compensated for (OR!)ñ Many (single tier) implementations with little fundamental research

Most failed and closed once public money stopped
ñ No ITS, no OR (or so little ...)
ñ Monaco introduces the CDC-consolidation-based system
17© Crainic 2022

30 – 25 Years + ... (2)þ OR-based R&D targeting the supply side initiated “with” the millennium
ñ 1999 First CL Conference (Institute for City Logistics, Kyoto U.)ñ Taniguchi at al. 1999

fFirst strategic design (location) paperñ Crainic, Ricciardi, Storchi 2004

fThe Two-Tier CL system; locating satellites
ñ Crainic, Ricciardi, Storchi 2009

fTactical-operational planning 2T-CL
fTime-dependent demand and operations
fScheduled Service Network Design + multi-period OD-demand VRPTW
fTwo-echelon multi-period OD-demand VRPTW
18© Crainic 2022

30 – 25 Years + ... (3)þ The ~25 of OR-based R&D for CL
ñ A few contributions only for the initial 10 years
ñ The pace increases significantly from 2010 onñ Continuously increasing flow of contributions

fProblem settings and new challenges
fModelling
fAlgorithmic development
fImplementations

19© Crainic 2022

Planning for City Logistics (Supply)
Decisions & Problem Settings

þ Consolidation-basedþ Many and varied

stakeholders
þ Single decision maker,
platform (at arm-length)
þ Not to be neglectedñ Demand planningñ Business models
ñ Cooperation understandings
ñ Politics, public policies
ñ Urban & regional planningñ Social & work relations
ñ Taxes & incentives, ...

Models & Algorithms
LocationLong-term Planning - Strategic
Organizational, business-model, physical, ...
System design and deployment, evaluation, ...
Plans & Guidelines

Location-routing
Location-design

Measures & Evaluations

Medium-to-Short-term Planning

Service Network
Design & Routing

Tactical (medium = “season”, 4-6 months)
Service design and resource management
Service and route selection, demand journeys, synchronization
Measures & Evaluations
Plans & Guidelines
Operational (short = “the day before”)
Tactical-plan adjustment and disaggregated planning
Plans & Guidelines

First/Last-mile
Routing
Pickup & Delivery
Multi-tier Routing

Measures & Evaluations

Execution
Dynamically in real-timeRe-organization/optimization of activities on new information

Sets of routes / itineraries

20© Crainic 2022

Individual route
Trip (Path) computation

System Representation for Multi-tier City Logistics Planningþ Need a system network representation to optimize the system (strategic) andthe service (tactical-operational), particularly for multi-tier nT-CL, 𝑛 ≫ 2(most current literature: 𝑛 = 2)
þ Two approaches (not very far, yet …)
þ Routing nE-VRP and variants (echelon = tier)ñ A routing problem on each tier
þ Service network design + routing
ñ Scheduled Service Network Design (SSND) on upper (1st, currently) tiers
ñ Vehicle Routing Problem(s) (VRP+ or approximations) on lower tiers
þ Rich, CL-particular, and complementRY problem settings
21© Crainic 2022

System Representation - City Logistics Routing
þ Multi-commodity with Origin-to-Destination (OD) demandþ Time-dependent demand (availability @ origins & due-date @ destination)⇒ Scheduled routes ⇒ Synchronization at satellites on multiple tiers
þ Multiple types of demand / traffic
ñ Inbound (classic; the most addressed)
ñ Outbound & local ⇒ Pickup & Delivery
þ Multi-tour (fleet management) routing / P&D
þ Multi-modal
ñ Line-based: light & heavy rail, buses & trolleybuses, barges
ñ No-line: trucks, cargobikes, drones, robots, on foot, ..., barges
ñ nE-VRP appears less appropriate for line-based modes
22© Crainic 2022

2T-CL – Routing Representation (inbound)
Cargo origin nodes

Primary facilities

P

P

P

First tier vehicles

S

S

S

Secondary Facilities

S

S

S

Second tier vehicles
Customers© Crainic 2022

System Representation - City Logistics Service Network Design
þ Time-dependent demand ⇒ Scheduled service routes
þ Synchronization at satellites (multiple tiers)ñ Vehicles of scheduled services and flows
þ Multi-modal: scheduled services on line-based and no-line modesñ Coexistence – “simultaneous” operation – with people service
þ “Large” vehicles, potentially compartmented (e.g., multi-door light rail)þ Multiple types of demand / traffic
ñ Inbound (classic; the most addressed), outbound & local
þ Fleet management: resource-to-service assignmentþ Lower tiers require routing approaches

24© Crainic 2022

2T-CL – Service Net Des Representation

External customer
zone
CDC
Satellite
City-freighter route
Urban-vehicle route25© Crainic 2022

Long-term Planning - Strategic
Organizational, business-model, physical, ...
System design and deployment, evaluation, ...
Location
Location-routing
Location-design26© Crainic 2022

Optimize the City Logistics System Design
þ Select among potential facilities on one or several tiers

fSelect interconnection network, e.g., street sub-networks for particular fleets
fFleet dimensioningþ Determine usage by services, routes, & demand flows
þ Min. Generalized cost of the system = selection + usage + impact on the city
þ Satisfy demand & enforce physical & operational system attributes & rules
þ Methodological approaches
ñ Location (allocation)
ñ Location-routingñ Location – service design
þ Few contributions yet, mostly single-tier location & based on routing
27© Crainic 2022

Facility Location (on a single tier)þ OD (multicommodity) demand matrix
þ Binary selection decision variable for eachpotential site
ñ Fixed (generalized) cost & capacity

þ Continuous flow (utilization) decisionvariables on each arc of the network
ñ Unit (generalized) transportation cost for eachcommodity on each arc
ñ Arc capacity (global and, possibly, by commodity)
þ Minimize total generalized cost of the system,

while movind the demand within the system
limitsMin å j f j y j + å j å i c ji x ji
s.a. x ji £ d i y j for all j , i
x ji £ u j y j for all j , iå x £ u y for all jå x = d for all i
i

ji

j

j

ji

i

j

y j = {0,1}x ji ³ 028© Crainic 2022

Facility Location (on a single tier)þ Combinatorial optimization formulation – “Location-allocation”
ñ Need to schematize journeys & approximate routing costs
þ Taniguchi et al. (1999)
ñ Single-tier, generalized system cost - pollution
ñ Bi-level idea: authorities locate, truckers decide usage
ñ Two linked models
þ Crainic, Ricciardi, Storchi (2004)
ñ Two-tier, satellite location onlyñ Generalized system cost

fUndesirability factor on nodes (sites) and arcs (streets)
fArc costs = min-cost path within street network
29© Crainic 2022

Location-Routing (LRP)þ Utilization = represent explicitly the network and the routing of vehicles

carrying freight out of / into selected facilities
þ Guyon et al. (2012) first CL LRP modelñ Single tier, fleet, inbound demandñ Generalized cost: environment and social impact
þ Most contributions: Locate on a single tier (multi-tier settings), inboundñ Gianessi et al. (2016): Locate facilities & a high-capacity ring + routingñ Boccia et al. (2018): Flow-intercepting LRP
fTake advantage of actual urban network and flow patterns
fLocate satelites to intercept the currently-known paths
fMany questions open !!
30© Crainic 2022

O1

O2

O3

O4

O1

O6

O5

O2

O3

O4

O6

O5

O1 - D1
O2 - D2O3 - D3O4 - D4O5 - D5O6 - D6
RoutesPossible locations
Located Facilities

D2

D2
D1

D4

D5

D6

D1

D3

D4

D5

D6
D3

Flows intercepted by 2 facilities further
towards destinations
Increased travel cost to reach the facilitiesàReduced travel cost to reach the destinationsàReduced routing costs

Flows intercepted by 3 facilities as near as
possible to the originàLow travel cost to reach the facilitiesàHigh travel cost to reach the destinationsàHigh routing costs
31© Crainic 2022

Facility Location on Multi-tier Systems
þ Locate on several tiers simultaneously: significantly more challenging
ñ Increased combinatorial nature (number of selection variables andlinking/feasibility constraints)
ñ More complex transportation issues
þ Easiest way: Multi-tier location-allocation with approximated inter-facility
and facility ↔ customer transportation costs
fStill difficult (linking decisions on several tiers)
fApplications in logistics network (supply chain) designþ More precise and challenging: Multi-tier location-routing

32© Crainic 2022

Multi-tier Location-Routing (nE-LRP)þ Boccia et al. (2010, 2011)
ñ Locate on two tiers
ñ Inbound single-commodity flow; no time – static setting
ñ Formulations:

3 (the most detailed) and 2 (somewhat easier to address) index arc models
1 (the one for “optimal” solutions via column generation) path modelþ Most contributions focus on meta- and matheuristics for this “basic” variant

33© Crainic 2022

pÎP
Hp
Kp
yp = {0,1}First echelon vehicles: g Î G
Vehicle Capacity:
UG
Vehicle Cost:
TCG
Vehicle variable:
tg = {0.1}
Routing cost:

CTij

Flow Variable:
Routing variables:
Satellite set:
Location Cost:
Capacity:
Location variable:
Customer Set:
Customer Demand:fps
rijg = {0,1}
sÎS
Hs
Ks
ys = {0,1}zÎZdz

Allocation variable:

wsz

Second echelon vehicles: v Î V
Vehicle Capacity:
UV
Vehicle Cost:
TCV
Vehicle variable:
Routing cost:

tv = {0,1}CTijRouting variables:

xijv = {0,1}

2nd echelon setting

Platform set:
Location Cost:
Capacity:
Location variable:

1st echelon setting

Illustration: A three-index FormulationPPP

Kp, Hp

yp

tg
f ps
g
g
CT gis r is

S

S

v

S

S K H ys
s,

s

w sz

tv
CT vsz x vsz ,dz© Crainic 2022

Illustration: A two-index Formulation
Second Echelon:
azv = {0, 1} à
bsv = {0, 1} à
wzs = {0, 1} à
xij = {0, 1} à

Assign vehicle v to customer z
Assign vehicle v to satellite s
Assign customer z to satellite s
Denote that customer i is visited
before customer j (i< j).

bsv

S

v
wjs

wis

Zi

First Echelon:
msg= {0, 1} à
npg = {0, 1} à
usp = {0, 1} à
rij = {0, 1} àaiv

Assign vehicle g to satellite s
Assign vehicle g to platform p
Assign satellite s to platform p
Denote that satellite i is visited
before satellite j (i< j).

ajv

xij

Zj

npg

P

g

usp
usp

msg

Si

rij

msg
Sj
© Crainic 2022

Multi-tier Location-Routing (2)þ Current work on multi-attribute 2E-LRP with synchronization (2E-MLRPS)

fEscobar-Vargas (PhD student finishing)þ Time-dependent OD demand

Availability (@ O) & due-date hard TW (@D)→ time dependency of routes (schedules)
þ Synchronize capacitated, tier-specific fleetsat (capacitated) satellites
þ Hybrid, discreet & continuous, time-space
network formulation
þ Dynamic Discretization Discovery methodology

Supplier
Platform
Satellite
Customer36© Crainic 2022

Multi-Attribute 2E-LRP
Static view

Time-sensitive view
Supplier
Platform
Satellite

Coordinates

Customer

Supplier
Platform
Satellite
Customer37© Crainic 2022

Nodes @ relevant periods

Time-Space Networks

System representation at period t

MovingHolding

Coordinates

Facility, customer, ... nodes“Classic” = all nodes @ all periods

Time
t -1

Period t

t+1

t + ...

38© Crainic 2022

Hybrid Time-Space Modelling

Coordinates

Figure 3: Hybrid representation of time for a single commodity case.

365

370

375

39

Define the following decision variables on G:
yi = 1, if facility i is open, 0 otherwise (location);
xij = 1 if arc (i, j) is selected, 0 otherwise (vehicle routing);kfijh= 1, if commodity k goes through arc (i, j) with vehicle h, 0 otherwikij = 1, if commodity k goes through the arc (i, j), 0 otherwise;µ1ih : Arrival time of first-echelon vehicle h at vertex i;µ2ik : Arrival time of commodity k at vertex i;1⌫ih: Departure time of first-echelon vehicle h from vertex i;
2⌫ik : Departure time of commodity k from vertex i .
The continuous-time variables needed to track vehicle schedules over the
space network in order to deliver the demand of customer c1 are illustrat
Figure 3, which also shows that only customer-to-customer connections arhandled by continuous time variables.
Let M be a large integer number. The hybrid 2E-MALRPS formu
then becomes:
X
X
X
X
min
Fi y i +Fi y i +⇣ij xij +⇣ij xij
i2P phi2Z ph1©(i,j)2A
Crainic 2022(i,j)2A2

370

1
⌫ih
: Departure time of first-echelon vehicle h from vertex i;
2⌫ik : Departure time of commodity k from vertex i .
The continuous-time variables needed to track vehicle schedules over the timespace network in order to deliver the demand of customer c1 are illustrated in
Figure 3, which also shows that only customer-to-customer connections are nothandled by continuous time variables.
Let M be a large integer number. The hybrid 2E-MALRPS formulation
then becomes:
X
X
X
X
min
Fi y i +Fi y i +⇣ij xij +⇣ij xij(1) facilities + route vehicles
SelectFormulation
375

i2P phSubject toi2Z ph(i,j)2A1

X

xij = 1 8c 2 C

X

j2Cc X
i2((C\Cc )[Z)
X

X

X(i,j)2A2xX
ij = 1 8c 2 C
xji 8c 2 C ph
j2Cc i2((C\Cc )[Z)2)
j2Cc X
j2Cc X
i2((C\Cj )[Z)i2((C\Cj )[E
X
X
X
X
X
xij =
x
8c 2 C phxijxhi 2 8jji 2 C
j2Cc i2((C\Cj )[Z)
j2Cc i2((C\Cj )[E )2)h2Cj X
i2((C\j)[Z)i2((C\Cj )[E
X
X
X x
X
x
8j 2 C
xijij xji 8j 2 Z hi
xij =

X

i2((C\j)[Z)i2E 2 X

X X

h2Cj i2((C\Cj )[E 2 )
i2C X

XX
8j 2
2Z
Zph
ji 8z
xij =xij 
xxji

2
i2C
j2Zz i2E 2 i2E
j2Zz i2C

X

X

i2((Z\Zj )[P)i2((Z\Zz )[P)X

xijh 
xijh =i2E 1

XX

h2H j2Z

xijh  yj
X 11

8j 2 Zxjih

1i2((Z\Zj )[E )

X

i2Z

xjih

8j 2 Z, h 2 H

8j 2 P, h 2 Hxijh  |K 1 |yi

8i 2 P

Single customer visit(33)(2)
Vehicleflow conservation at customers (2nd tier)
(34)
(3)
(35)
Don’t
leave a customer before ending service(4)(36)
An inbound 2-tier vehicle @ satellite for an outbound vehicle to customers(5)(37)
Vehicle flow conservation at satellites(38)
Visits at open satellites only(39)
An inbound 1-tier vehicle @ satellite for an outbound to satellite/garage(40)
Vehicle flow conservation on 1st tier(41)
Fleet size @ platforms

40© Crainic 2022

X X

k
fijh
= 1 8k 2 K, j 2 Z(42)

Unsplit demand

k
fijh
 yp

(43)

Leave from selected platformh2H i2P0 (k)

X

X XX

h2H i2Pp j2Z

X

X

k
ij

j2Cj

X

h2H j2Zz i2((Z\Zj )[P)X

X

h2H i2((Z\Zj )[P)kji = 0

8j 2 C ph , k 2 K, j 6= dki2((C\Cj

8j 2 C , k 2 K, j 6= dk

X)[E 2 ) j2C

X

k
ji =

X

h2H j2Zz h2((Z\Zj )[E 1 )X

Xi2((Z\Zj )[P)

X

k2K

X

h2H

k
fjdh
+
1

h2H h2((Z\Zj )[E )

wk

k2K

X

X

k2K

wk

wk

X

X

i2Z

k
fijh
 cap1kij  cap2Xkij  xij

Commodity flow conservation @ customers(45)

Commodity flow conservation @ destination

xijh

j2Zz l2(C)

X

l2(C)

k
jl

(46)
k
jl

8z 2 Z ph , k 2 K Commodity flow conservation @ satellites(47)

8j 2 Z, k 2 K (48)

8j 2 Z, h 2 H(49)

8j 2 C,

(50)

k
fijh
 ⇥ p yi

8i 2 P(51)

8k 2 K, h 2 H, (i, j) 2 A1(52)

h2H j2(Z\Zj )kfijh
 xijh(44)i2((C\Cj )[Z) j2Cjj

8j 2 C ph , k 2 K, j = dk
X X
X
X X
k
k
fijh
=
fjh
+

k
fijh


X

j2Cj

k
ij

ph

xji

X

i2((C\Cj )[Z) j2CjXXkji  1

j2Cj

X

X X

X

i2((C\Cj )[E 2 ) j2Cj

i2((C\Cj )[Z) j2Cj

X

X

k
ij

8k 2 K, p 2 P ph

8k 2 K, (i, j) 2 A

2Vehicle synchronization (space & time) @ satellites
Vehicle capacity @ each tier
Vehicle flow conservation on 1st tier
Link commodity and vehicle flows

(53)

41
© Crainic 2022

Formulation (3)
1
⌫ih

X

j2Z
2
⌫jk

µ1jh

(2

k
jd(k)

k
↵ik fijh

8h 2 H1 , k 2 K, i 2 P

X

k
fijh
)M

8k 2 K, h 2 H1 , j 2 Z

(55)

k
fijh
)M

8k 2 K, h 2 H1 , j 2 Z(56)

i2(Z[P),i6=j
1
⌫jh

µ2jk

(2

k
jd(k)

X

i2(Z[P),i6=jµ1ih + ⌧ij
1
⌫ih
+ ⌧ij

k
µ1jh  (1 fijh
)M 8k 2 K, h 2 H1 , (i, j) 2 A1k
µ1jh  (1 fijh
)M 8h 2 H1 , k 2 K, (i, j) 2 A1k
µ2ik + ⌧ij µ2jk  (1
8k 2 K, (i, j) 2 A2
ij )M
2
k
⌫ik
+ ⌧ij µ2jk  (1 fijh
)M 8k 2 K, h 2 H2 , (i, j) 2 A212⌫ih
µ1ih  Wmax
8h 2 H1 , i 2 Z
22⌫ikµ2ik  Wmax
8k 2 K, i 2 Z
ai  µ2ik  bi 8i 2 C ph , k 2 D(k)

380

385

(54)

(57)

Departure from platform once commodity is available
Arrival 1st and 2nd tier vehicles @ satellite for synchronization
Arrival & departure times 1st tier vehicles

(58)
(59)

Arrival & departure times 2nd tier vehicles

(60)
(61)
(62)

Waiting time limitation @ satellites(63)

Customers visited within their time windows

The objective function (1) minimizes the total cost of the system, including
the fixed cost of selecting (opening) facilities on both echelons and the variable travel costs of the vehicles on both echelons to move the demand flows.
Constraints (2) ensure that each customer can be visited only once. Equations(3) are conservation constraints on routing variables for customers. Constraints(4) impose that outbound connections to customers must take place after theirrespective service time. Constraints (5) enforce that, for each outbound connection from a satellite to a customer, there is an inbound connection from asecond-level vehicle garage to the satellite, including the waiting times at
42thesatellite. Equations (6) are conservation constraints on routing variables for each

© Crainic 2022

Dynamic Discretization Discovery (DDD) Solution Methodþ The precision of time-space models & the computational challenges ofaddressing them grows as granularity (number of periods) grows !
þ DDD idea (Boland et al. 2017)
ñ Start with coarse granularity (sparse time-space network)ñ Iteratively refine the granularity (add nodes and links)
fCompute bounds by solving the formulation on the restricted network
þ Applied quite successfully to “standard” Service Network Design
þ Work underway to generalizeþ Multi-attribute location-routing quite challenging but appears successful

43© Crainic 2022

Medium-to-Short-term Planning
Tactical (medium = “season”, 4-6 months)
Service design and resource management
Service and route selection, demand journeys, synchronization
Measures & Evaluations
Plans & Guidelines
Operational (short = “the day before”)
Tactical-plan adjustment and disaggregated planning

Service Network Design & RoutingFirst/Last-mile Routing
Pickup & Delivery
Multi-tier Routing
44© Crainic 2022

Tactic-Operational City Logistics Planningþ Medium-to-short term planning = Plan regular operations, based on a(point) forecast, for efficient resource allocation & utilization, customer
satisfaction, profitable operations for stakeholders, citizens, the city
þ Select services, routes (tours), and schedules + terminal activities at all tiers
þ Select OD demand itineraries through the service network
þ Manage and synchronize resources, facilities & fleets, at all tiers
þ Minimize total (generalized) cost of the system
þ Satisfy the demand within the agreed time restrictions
þ Physical & operational requirements and limitsþ Plan for a schedule length, repeatedly applied over the planning horizon, orfor the next operation period (“tomorrow”)
45© Crainic 2022

Tactic-Operational City Logistics Planning (2)þ One must account for Demand & Supply knowledge / forecast confidenceñ How large variations? How regular? How reliable? Þþ From no-plan (high variance + no confidence): Not in CL literatureñ Dynamic fleet management
þ To confident plan (low variance or high confidence)ñ Deterministic formulations
ñ Most contributions
þ Through various formulations, e.g., Stochastic, accounting for uncertainty

fPlan main resources & services (1st stage)
fOn-the-day routing adjustments/recourses (2nd stage)f(Crainic et al. 2016)
ñ Not much, yet!
46
© Crainic 2022

Routing & Tactic-Operational CL Planningþ Single-tier systems & last-mile delivery (first-mile pickup)
ñ CVRP/VRPTW variants for a few CL attributes, e.g., returns to satellites

for reloading, crowdsourcing, ...
ñ Many new hardware (vehicles, lockers, ...) technologies
ñ Evolving people behaviour and requirements⇒ e-commerce clash with CL sustainability goals
ñ Challenge of integrating into CL framework & goals
þ Multi-tour pickup & delivery on given tier with multiple demand types andmultiple visits to satellites to load/unload/exchange loads (synchronize)➞ the pseudo-backhaul policy(Crainic et al. 2012, Nguyen et al. 2013, 2016, Bettinelli et al. 2019)47© Crainic 2022

Routing & Tactic-Operational CL Planning (2)þ nE-VRP for CL not much work yet ...
þ 2E-VRP formally defined as extension of CVRP (Perboli et al. 2011):

single CDC & inbound (single) commodity
ñ Much algorithmic work on the basic settingñ Few (if any) CL attributes
þ Arc and path models for multi-attribute 2E-VRPTW with time-dependent
OD demand, scheduled routes (1st tier), multi-tours (2nd tier), andsynchronization (Crainic et al. 2009)
ñ Algorithmic work addressing groups of attributes
ñ Currently: OD demand (multi-commodity) and TW (Dellaert et al. 2021)
48© Crainic 2022

SSND & Tactic-Operational CL Planningþ Multi-period, time-space network formulations
þ Time-dependent inbound, outbound, internal OD demandþ SSND (-RM) +VRP(TW) (Crainic et al. 2009)
ñ Scheduled service network design with resource management

fNo-line and line-based scheduled potential services on top tiers (currently 1st tier)ñ nE-VRP / P&D on lower tiers

fmultiple-tour P&D vehicle routes
ñ Synchronization (at satellites)þ SSND (1st tier) + approximate routing costs (Fontaine et al. 2020)
ñ Customers linked to satellites with approximated routing costs
ñ Distribution of demand: select OD itinerary = assignment to (service,compartment, satellite) combination, implicitly selects the CDC as well49
© Crainic 2022

Select Services, Routes, Itineraries in Time

City-freighter route

Urban-vehicle service
O-D customer
itinerary50© Crainic 2022

Scheduled Urban-Vehicle Services
Which service to run, when? r(r) Î {1,0}sz’

r: t(r)=t+1
zr’: t(r’)=t
r: t(r)=t; s(r) = {z,z’}
r’: t(r’)=t; s(r)={z}51© Crainic 2022

City-freighter Possible Movements – Timing (inbound)
st

d(i)

Cst

st+

s’’t+

i
Which work assignmentsj(h) ≥ 0 to operate?

d(j) jk d(k)

Time windows
Service times

gt

s’t+

gt+

Arrive ontime !!

gt++
52© Crainic 2022

City-Freighter Work Segment & Work Legs (inbound)e’t’

e’’t’’

e’’’t’’’

c2
c3
c4

c1
st
c1

c5
c6
c7
c8

s’t+

j(h) Î{1,0}

c3

c8

c2
gt-

c4

Which
c-f work assignment
to operate?

c6

c7
c5

g’t++
© Crainic 2022

Integrated Routing with Pseudo-Backhauls
Waiting station w1

s2

s1

g
𝑝#

𝑝$

𝑝$

𝑑#
𝑝"

𝑝!

𝑑$
𝑝%

d1 d
2

𝑑" 𝑑%

d3
𝑑!

𝐷#$

Local
(pickup &delivery)

𝑝#
𝑑#

𝑝"

𝑑$

p6 p7

𝑝%
𝑑"

d4

𝑃!"! ∪ 𝐷!"!
t ∈ [t1(s1), t2(s1)]

g

𝑝!

𝑑%
𝑑!

𝑃!"! ∪ 𝐷!"!

Local
Inbound(pickup &(delivery)
delivery)

p8

d11
p9
p10

𝑃##

d14

d12
d15
d13

𝐷##

t ∈ [t1(s2), t2(s2)]Time

Outbound(pickup)54© Crainic 2022

Demand Itineraries
Select itinerary todeliver cargo on time:z(m) Î {1,0}z’dzm:{e,r(m),t(m) < t(r),z(m)=z(m)Î s(r(m)),
n(p(d)), l(h(m)), c(d)}d: e,c,p,t,[a,b],vol55e© Crainic 2022

The Model
Framework

Generalized cost
first-tier services

Generalized costsecond-tier work assignments
Linking – u-v capacity
Linking – c-f capacity
Single itinerary

Satellite capacity for u-v & c-f

c-f fleet size

56
© Crainic 2022

Tactical Planning Modesþ What regularity?
ñ Clear for first tier: major flow corridors & resources, terminals, masstransport modes, …
ñ Less clear for second-tier routing, where day-to-day variations are thenormþ Thenñ Model for the day-before planning problem
ñ Approximate second-tier routing for medium-term tactical planning, orñ Second-tier routing as recourse in stochastic model57© Crainic 2022

Day-before Tactical Planning Modelling (in & out)þ Selection of services

r(r) Î {1,0}þ Distribution of demand: select OD itinerary = assignment to (service,compartment, satellite) combination, implicitly selects the CDC as wellx(rc,d,z) = 1, if demand d is assigned to compartment rc and satellite z; 0, otherwise

þ Min generalized (operations + impact on city) costs
58© Crainic 2022

Formulation
Service selection

Demand assignment to (compartment, service, satellite, CDC

Unsplit delivery
Inbound before outbound
Vehicle capacities
Vehicle availability
Satellite capacities:• Total vehicles• Per mode•

Transferred volume
59© Crainic 2022

Solution Methods
þ Heuristics proposed for full formulation – lots of work to do !!
þ Benders decomposition for first tier appears to work well
þ Complicating variables: the design variables 𝜌 𝑟
ñ Master problem selects scheduled services!
þ Easier variables: the assignment variables 𝑥 𝑟 , 𝑑, 𝑧ñ Slave subproblem: multiple knapsack with precedence constraints

fLinear relaxation = very good lower bounds ➞ tight cuts60
© Crainic 2022

A Few Insightsþ Multimodality significantly reduces costs and the numbers of services andvehiclesþ Multi-compartment line-based modes are very beneficial and efficientþ Integration of inbound and outbound is beneficial
þ Many challenges still ahead

61© Crainic 2022

Research Perspectives
þ Modelling the full array of CL characteristics yielding

formulations consistent over all planning levels,
which can be efficiently addressed for realistic problem dimensions
þ Modellingñ Representation of nuisance and impacts
ñ Multi-tier, multi-modal settings with inbound, outbound and local demandñ Business/collaboration models (sharing risks, costs, profits, …)
ñ “New” technology and operation modes on last/first-mileñ Approximating costs and times of multi-attribute (multi-tier) routing
ñ Synchronizing multiple scheduled service network design, routing, andterminal services
ñ ...
62

© Crainic 2022

Research Perspectives (2)þ Uncertainty, resilience, recovery (disturbing events), & revenue management
ñ Important issues for freight transportation and logistics
ñ Research in this area promises to yield substantial benefits for bothscience and applications
ñ Uncertainty
fDemand, travel and service times
fCorrelations
fSynchronization
þ Adapt generic models to particular cities and countries ...

63© Crainic 2022

Research Perspectives (3)þ Solution methods for deterministic and stochastic models
ñ Exact (validation) & meta/math-heuristic (actual use)

fDecomposition methods (of path and arc-based models)e.g., projecting synchronization relations on tier-specific subproblems
fDynamic generation of services and pickup and delivery routes
fDynamic generation of multi-tier space-time SSND + P&D network
fParallel exact and collaborative search matheuristics
þ Cost and benefit analyses (multiple conflicting objectives)
þ Integration of urban/regional planning of people, freight, and CL transport

64© Crainic 2022

General Perspectives
þ The issue of freight transportation in urban areas is here to stay and grow
þ What systems and business models for each country and (very) large cities?
þ Private and public initiatives
þ City Logistics and logistics chains? E-commerce?
þ What freight transportation systems for the future?
þ The challenge ofreconciling “theoretical” efficiency-quality, citizen andpolitical behaviour and acceptance, and managerial activity and ease-of-use

65© Crainic 2022

Proposed by the Team from Three Japanese Universities

66© Crainic 2022