Operational planning for many-to-one-to-many freighttransportation

W. Guoa,b,c∗ , T.G. Crainica,b , M. Gendreaua,d and W. Reia,ba <CIRRELT - Interuniversity Research Centre on Enterprise Networks, Logistics andTransportation>, <Montréal>, <Canada>b <Analytics, Operations, and Information Technology Department, Université du Québec àMontréal>, <Montréal>, <Canada>c <School of Transportation and Logistics Engineering, Wuhan University of Technology>,<Wuhan>, <China>

d <Department of Mathematics and Industrial Engineering, École Polytechnique deMontréal>, <Montréal>, <Canada>
guo.wenjing@courrier.uqam.ca, TeodorGabriel.Crainic@cirrelt.net
michel.gendreau@cirrelt.net, rei.walter@uqam.ca∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island
April 12, 2022

Keywords: M1M systems; Operational planning; Look-ahead model; Rolling horizon framework;
Adaptive large neighborhood search heuristic

1INTRODUCTION

Transportation and Logistics (TL) systems that provide movements of freight and passengers
over regional, national, or international networks are essential to society's development andachievements. Traditionally, freight transport systems are managed by multiple stakeholders thatorganize the movement of goods over part of the TL chains independently without information
and resource sharing, which causes empty travels, low capacity utilization, high transportation
costs, delay in deliveries, and heavy carbon emissions. With the development of informationand communication technologies and intelligent transport system technologies, new TL businessmodels, such as City Logistics (Savelsbergh & Woensel, 2016), Physical Internet (Pan et al.,2017), and Synchromodality (Giusti et al., 2019), have been proposed to address these issues.
The common feature of these innovative systems is to provide ecient, eective, and sustainable
services through the coordination and cooperation of stakeholders, the consolidation of shipmentows, and the synchronization of operations in integrated networks driven by intelligent `decisionmaking' platforms.
To answer the needs in more than one application environment, this paper proposes a manyto-one-to-many (M1M) freight transport system that integrates rst/last mile urban distribution and long-haul multimodal transportation for shipments with standard loading units (e.g.,π -containers). On the one side of the M1M system, many shippers (e.g., producers, wholesalers,and distributors) make shipment requests for cost and time-ecient transportation of their product loads. Each shipment needs to be transported from a given shipper location to a consignee
location within given time windows. On the other side, many carriers (e.g., transportation service providers), of diverse modes and types (full or less-than-truckload motor carriers, railroads,
TRISTAN XI Symposium

Original abstract submittal

W. Guo, T.G. Crainic, M. Gendreau and W. Rei

2airlines, and river and ocean navigation, etc.), make service oers for urban and long-haul transportation and request protable loads. Each service provides a limited transport capacity on aspecic route with or without time schedules, served by one or multiple vehicles with the sameor dierent modes. In the middle, the one - using the Intelligent Decision Support Platform(IDSP) for `automated' planning and optimizing operations - aims to protably and simultaneously satisfy the needs of both categories of stakeholders. The IDSP receives requests andoers continuously over time and optimizes in time and space the selection of shipment requests
and service oers, shipment-to-service assignments, shipment itineraries, and service schedules
through consolidation of shipments of dierent shippers into the same vehicles and synchronization of activities in an interconnected transportation network, as illustrated in Figure 1. The
recent developments in information technologies such as cloud computing and Internet of Things
allow real-time monitoring of shipments' and vehicles' status and information sharing among
stakeholders, which facilitates the adoption of such a platform in practice.

Shippers

Shipment requests

Decisions(yes/no, when, how = itinerary)

IDSP

Service offers

Carriers

Decisions(yes/no, when,what = vehicle loads = set of shipments)

Monitoring & info
it left, on its way, it arrived & status

Interconnected transportation network

Figure 1  M1M system structure, stakeholders, communications & decisions

To the best of our knowledge, this is the rst paper that considers the selection of shipment
requests and service oers simultaneously in freight transportation at the operational level. To
bridge this gap in the literature, the rst contribution of this paper is that we introduce aplatform that integrates the decisions on acceptance or postponement of shipment requests andservice oers, and decisions on shipment-to-service assignments, shipment itineraries, and service
schedules for accepted requests and oers. Besides, we consider both requests and oers arriveat the platform dynamically. The decisions made now may have an impact on the future,what happens in the near future may also inuence the decisions we take now. To reect theinterplay between current decisions and future outcomes, we develop a look-ahead model that
integrates predicted requests and oers into decision processes. Thanks to the development ofdata analytics, the platform can obtain trusted predictions of near-future events. Furthermore,
the decisions made at each time are not all to be put into practice. This paper designs arolling horizon framework to control the implementations and re-optimize the decisions when
new requests and oers are received. To produce good-quality solutions rapidly, an adaptive
large neighborhood search (ALNS) heuristic algorithm is designed to solve the optimization
problems at each decision time. Finally, we conduct extensive numerical experiments to evaluate
the performance of the look-ahead model in comparison to a myopic model that does not take into
account future outcomes, and assess the eciency of the ALNS heuristic in terms of computation
time and solution quality.
TRISTAN XI Symposium

Original abstract submittal

W. Guo, T.G. Crainic, M. Gendreau and W. Rei
2METHODOLOGY

2.1

Look-ahead model

3

The evolution of the M1M system is indexed by a discrete time variable t ∈ [0, ..., ∞). We denotetime period t ∈ [1, ..., ∞) as the duration from time t − 1 to time t. Requests and oers received
during time period (t − 1, t] will be kept until decision time t ∈ [1, ..., ∞).
Under the look-ahead context, at any time t, decisions are made over a planning horizon T
based on known as well as predicted information. We denote H as the length of the prediction
horizon, H ≤ T . The decisions made at any time t can be divided into four groups: 1) acceptancedecisions, which indicate whether active or predicted requests/oers are accepted or postponed
at time k ∈ {t, ..., t + T }; 2) assignment decisions, which indicate whether a shipment is assigned
to a service segment at time k ; 3) service schedules, which indicate the departure times of timeexible services at their origins; 4) shipment schedules, which indicate the time a shipment ispicked up, unloaded, crossdock moved, stored, loaded, and delivered over the planning horizon.
The objective of the look-ahead model is to maximize the total prots for known and predicted
requests and oers over the planning horizon, including: the fare for accepted requests; the xedcosts for accepted oers; the transportation costs; the pickup costs at origins; the delivery costs
at destinations; the unloading, crossdock movement, storage, and loading costs at intermediate
terminals; and the penalty costs for early and later delivery of shipments. The constraints of themodel can be classied into four sets: 1) acceptance constraints, which ensure each request/oer
can be accepted at most once within its feasible acceptance horizon; 2) ow constraints, which
ensure an accepted shipment will be picked up at its origin and delivered at its destination
within given time windows in addition to ow conservation at intermediate terminals; 3) service
scheduling constraints, which ensure each time-exible service will depart from its origin within
its start time window; 4) capacity constraints, which ensure the loads at service segments andactivities at terminals will not exceed the maximum capacity limitations.

2.2

Rolling horizon framework

At any time t, decisions suggested by the optimization model are not all to be implemented. We
distinguish between the current implementation and the look-ahead components of the planninghorizon. The acceptance decisions made at time t are generally implemented, that is, they are not
to be changed in the follow-up periods, and are transmitted to the appropriate stakeholders anddepartments of the IDSP's rm for execution; but the decisions regarding shipment-to-service
assignments, shipment itineraries, and service schedules made at time t are changeable if theshipment will not be picked up before time t + 1 and the service will not depart before time t + 1.
Period t + 1 thus belongs to the current implementation component of the planning horizon. The
following periods, from period t + 2 to period t + T , belong to the look-ahead component. Most
decisions of these periods are temporary in nature, they are not to be actually put into practiceand executed.
Based on the decisions made at time t, for accepted requests that will depart before the next
decision time t + 1, shipments' itineraries and schedules are xed. The platform thus needs tobook the transport, loading, unloading, crossdock movements, and storage capacities required
for the shipments; for time-exible services that are assigned to shipments whose itineraries arexed, their time schedules will also be xed, the platform thus needs to inform carriers thescheduled departure, arrival and return times. After implementing the xed decisions made attime t, the platform achieves a new state at time t + 1. Such a procedure is used repeatedly, as
time advances and the planning horizon is pushed into the future, as shown in Figure 2. This iscalled the rolling horizon procedure.
TRISTAN XI Symposium

Original abstract submittal

W. Guo, T.G. Crainic, M. Gendreau and W. Rei

4Dynamic requests and offers
𝔯2𝔬1
𝔯1

1234

56…

𝑡𝛼 A (𝔯)𝛼 A (𝔬)𝛽 A (𝔯)𝛽 A (𝔬)𝛽 L (𝔯)𝛽 L (𝔬)Time

1Current
implementation

2
Prediction horizon H=33Decision time

Planning horizon 𝑇 = 5Figure 2  Rolling horizon framework for the operational planning of the M1M system
2.3

Adaptive large neighborhood search heuristic

Due to the computational complexity, we design an adaptive large neighborhood search (ALNS)
algorithm to solve the optimization problems at each decision time. The ALNS algorithm consists of two layers: the rst layer selects requests and oers; the second layer decides shipment
itineraries and service schedules. Based on the properties of the M1M problem, we design adapted
removal and repair operators to improve the solutions at each layer.
3RESULTS

The performance of methodologies is tested under a comprehensive set of instances. Specically,
we compare the look-ahead model with a myopic model which does not consider future outcomes;
we compare the ALNS heuristic with the CPLEX solver.
4DISCUSSION

At the conference, we will introduce the operational planning problem of the M1M systems inwhich an intelligent decision support platform aims to provide optimal decisions on acceptanceor postponement of shipment requests and service oers, and decisions on shipment-to-service
assignments, shipment itineraries, and service schedules for accepted requests and oers. We will
discuss the look-ahead model that integrates forecasted requests and oers into decision processes.
A rolling horizon framework will be proposed to control the implementation and reoptimizationof decisions. Finally, we will show the adaptive large neighborhood search algorithm that solves
the optimization problems at each decision time. The performance of methodologies will bediscussed under a comprehensive set of instances.
References
Giusti, Riccardo, Manerba, Daniele, Bruno, Giorgio, & Tadei, Roberto. 2019. Synchromodal logistics:
An overview of critical success factors, enabling technologies, and open research issues. Transportation
Research Part E: Logistics and Transportation Review, 129, 92110.
Pan, Shenle, Ballot, Eric, Huang, George Q., & Montreuil, Benoit. 2017. Physical Internet and interconnected logistics services: research and applications. International Journal of Production Research,55(9), 26032609.
Savelsbergh, Martin, & Woensel, Tom Van. 2016. 50th Anniversary Invited ArticleCity Logistics:
Challenges and Opportunities. Transportation Science, 50(2), 579590.

TRISTAN XI Symposium

Original abstract submittal