Logic-Based Benders for intermodal operations with delay penalties Ioannis Avgerinos1 Ioannis Mourtos1 and Georgios Zois1 1ELTRUN Lab Department of Management Science and Technology Athens University of Economics and Business

2025-04-24 0 0 817.3KB 26 页 10玖币

侵权投诉

Logic-Based Benders for intermodal operations with delay penalties

Ioannis Avgerinos1,*, Ioannis Mourtos1, and Georgios Zois1

1ELTRUN Lab, Department of Management Science and Technology, Athens University of Economics and Business,

Patision 76, 10434, Athens, Greece E-mail: iavgerinos@aueb.gr, mourtos@aueb.gr, georzois@aueb.gr

*Corresponding Author

Abstract

Intermodal logistics typically include the successive stages of intermodal shipment and last-mile delivery.

We investigate this problem under a novel Logic-Based Benders Decomposition, which exploits the staged

nature of the problem to minimise the sum of transport costs and delivery penalties. We establish the

validity of our decomposition and apply eﬀective optimality cuts. Apart from models and formal proofs, we

provide extensive experimentation on random instances of considerable scale that shows the improvement

achieved in terms of small gaps and shorter time compared to a monolithic MILP approach. Last, we propose

a major extension of our generic method for a real logistics case. The implementation of the extension on

real instances show the versatility of our method in terms of supporting diﬀerent planning approaches thus

leading to actual cost improvements.

Keywords. Logistics, Benders decomposition, intermodal transportation.

1 Overview and Background

The operation of functional distribution networks remains a major challenge in freight transportation, as in-

dicated also by the COVID-19 outbreak, which required acute response to severe disruptions. A report of

the International Finance Corporation of the World Bank Group [20] lists the closure of the borders between

Germany and Poland and the shortage of truck drivers in India as two events that challenged the endurance

of the logistics’ providers. The increase of railway freight transports, as a response to the radical decrease of

air freight capacity between China and Europe during the pandemic [20], shows that using alternative modes

of transport could tackle such challenges. In parallel, Direct Supply Chains [28] aim at dynamically shaping

Supplier - Organization - Customer routes that minimize both the operating costs and the delayed deliveries.

As the last-mile stage of the chain, in which the delay penalties are involved, is determined by the intermodal

transports of the preceding middle-mile stage, a proper coordination between these two stages is required.

In this study, we aim at minimizing the total transportation costs and delivery penalties of a logistics supply

chain by an exact optimization method that ﬁnds provably near-optimal solutions in realistically-sized instances

in reasonable time. For that to happen, the intermodal transportation and the last-mile deliveries must be si-

multaneously planned as heavier transport costs occur in the former stage, whereas delays are realised in the

latter. A Mixed-Integer Linear Programming (MILP) model is intractable for a commercial Integer Program-

ming solver and this is where our technical contribution comes forward. That is, we propose a Logic-Based

Benders’ decomposition (LBBD) [18, 19] of the two-staged problem, motivated by the recent LBBD literature

arXiv:2210.05592v1 [math.OC] 11 Oct 2022

on supply chain problems (e.g., [3, 36]). In our LBBD, the so-called master problem handles the intermodal

transportation problem, whereas a set of subproblems handles the last-mile delivery. Further aspects of interest

include the introduction of appropriate optimality cuts plus subproblems’ relaxation and valid inequalities, all

aiming at strengthening the master problem’s formulation. In particular, inspired by a modern concept of de-

composition schemes, namely Partial Benders decomposition, we retain information of the subproblems to the

master problem, so that a faster convergence is achieved.

Relevant Background. Cross-docking is a logistics concept which includes consolidation points for the

orders, as intermediate stations between the supplying points and the customers. A comparison of the cost-

eﬀectiveness of Cross-Docking and the regular direct-shipment policy is provided by [31], and a model that

combines both approaches is described by [7]. Since Cross-Docking operations occur in our setting, we draw

ideas from [40, 32]. An extended survey on the inclusion of intermediate facilities in freight transport networks

appears in [17]. If the network includes multiple Cross-Docking stations, the multi-depot Location-Routing

problem of [39] and the multi-depot VRPTW of [24] would be of value.

Intermodal networks have long been studied under an optimisation viewpoint [26]. This is not surprising

because they include several alternative topologies [38] and network designs. Notably, our work considers a

hub-and-spoke layout, that is the direct shipment of orders from hubs to customers. In addition to the selection

of the means of transport that will perform the shipment, a logistics supply chain must also consider the delays

of the deliveries: indicatively [21] considers ﬁxed arrival rates and transport times to compute the delays of

the deliveries in a USA road-rail intermodal network. An intermodal network typically includes timetabled

transport services of diﬀerent modes (rail or ship), in which each service can be performed during multiple

time windows in a planning horizon. As this is also the case in our study, we extend the approach of [29]

that constructs identical copies of transport services that depart in diﬀerent time instances. Time aspects are

important also for the hub location problem in an intermodal network [4].

Recently, [15] oﬀer a heuristic for transferring hazardous materials through a network of railway or roadway

nodes, thus solving a routing problem under stochastic scenarios. [12] aim to connect inland hubs with ports

through a network under strict time windows, so that a set of containers is shipped by the sea terminals. While

the model of [12] considers containers that are already loaded, the study of [25] includes hubs that are also

charged with the consolidation of orders to vehicles before the latter are routed through a multi-modal network.

All three studies examine realistic instances that are signiﬁcantly larger than the ones previously examined in

the literature. Therefore, these papers suggest heuristic methods, since a commercial solver cannot respond

in reasonable time. We are quite motivated by these developments, as our approach can handle instances of

analogous size and of broader scope.

The literature on intermodal transportation is enormous, yet the one summarized in Table 1 shows the use of

multiple optimization methods. Although heuristic methods remain of great value, the contemporary landscape

reveals that 3PL provider compete on total cost, thus ﬁnding the optimal solution matters. Exact methods are

known to be slow or inappropriate in terms of memory requirements, thus our work exploit the staged nature of

our problem to apply a decomposition scheme. Decomposition-based methods are widely used in transportation

problems, some of them being intermodal [14, 16]. The main framework of our exact approach for this paper

will be Benders Decomposition [9] and, in fact, its logic-based extension [18] (LBBD). The closest study relying

on LBBD is [27], although LBBD has broad applicability [33]. Beyond modelling, the implementation of LBBD

is a non-trivial task as its success depends on the integration of valid cuts and also the combination of MILP

and Constraint Programming (CP) formulations, as nicely discussed in [22]. Recently, the concept of Partial

Reference Description Solution Approach

Wu et al., 2002 [39] Multi-depot Vehicle Routing Problem Heuristic, TS

Rousseau et al., 2004 [26] Vehicle Routing Problem with Time Windows CG, CP

Moccia et al., 2011 [29] Intermodal Transportation Problem CG, BnC

Alumur et al., 2012 [4] Intermodal Hub Location Problem MIP

Ishfaq & Sox, 2012 [21] Intermodal Network Design Heuristic, TS

Li et al., 2014 [24] Multi-depot Vehicle Routing Problem GA, LS

Ghane-Ezabadi & Vergara, 2016 [16] Intermodal Network Design Decomposition

Yu et al., 2016 [40] Vehicle Routing Problem with Cross-Docking MIP, SA

Nikolopoulou et al., 2017 [31] Cross-Docking and Direct Shipment Comparison LS

Wang & Meng, 2017 [37] Intermodal Network Design Nonlinear Algorithm, BnB

Ghaderi & Burdett, 2019 [15] Intermodal Transportation Problem Heuristic

Mah´eo et al., 2019 [27] Transit Network Design BD

Azizi & Hu, 2020 [7] Pickup and Delivery Problem with Location Routing MIP, BD

Belieres et al., 2020 [8] Logistics Network Design BD

Fazi et al., 2020 [12] Pickup and Delivery Problem with Location Routing Heuristic, TS

Avgerinos et al., 2021 [6] Intermodal Transportation Problem BD

Fontaine et al., 2021 [14] Intermodal Transportation Problem BD

Li et al., 2021 [25] Intermodal Transportation Problem Heuristic

Qiu et al., 2021 [32] Vehicle Routing Problem with Cross-Docking BnC

TS Tabu Search

CG Column Generation

CP Constraint Programming

BnC Branch-and-Cut

BnP Branch-and-Price

MIP Mixed Integer Problem

LS Local Search

GA Genetic Algorithm

SA Simulated Annealing

BnB Branch-and-Bound

BD Benders Decomposition

Table 1: Summary of literature on Routing and Intermodal Transportation Problems

Benders Decomposition, that is addition of information derived from the subproblem to strengthen the master

problem, has been implemented on stochastic network design problems [10]. As [8] and [14] also did for their

presented logistics network design problems, we implement this idea on our decomposition setting.

Our contribution. To the best of our knowledge, this is the ﬁrst paper oﬀering an exact approach that

considers together the intermodal transportation stage and the last-mile delivery of a Direct Supply Chain.

Unifying these two stages allows us to consider the delayed delivery penalties, which are signiﬁcantly determined

by the preceding intermodal transportation, but nevertheless charged during the last-mile delivery.

From an application-oriented standpoint, we experiment with large-scale randomly generated instances,

with 60 −160 orders. These orders are transferred through a network of 7 hubs, connected with hundreds of

intermodal services. Let us note that [16] solve instances of 150 orders, consolidated in 4 hubs and transferred

by combinations of 3 modes per connected pair of hubs, while [25] address the shipment of 300 orders to a

network of 20 nodes; [12] consider datasets of 600 containers, nevertheless their network is unimodal. Thus, our

instances are comparable with the largest in the intermodal transportation literature. In addition, we expand

the scope of the typical intermodal network planning problem, by considering penalties of delays in the objective

function.

To evaluate the eﬃciency of our method under the additional complications imposed by a real-life application,

we extend our formulations to an actual case of a 3PL provider in Europe. This case integrates all three stages

of a logistics supply chain (i.e., ﬁrst-mile,middle-mile,last-mile). For the last-mile stage, two alternative

conﬁgurations are used. Our method exploits the fact that the practical restrictions of the problem allow us

to pre-compute ﬁxed routes for the ﬁrst and last-mile stages, thus modelling the corresponding vehicle routing

problems as exact-covering or resource-constrained scheduling problems. The extended LBBD algorithm is

evaluated, after being implemented on real instances, given by the logistics provider. This paper is a strongly

enhanced generalisation of [6], whose experiments on smaller instances show already that a commercial solver

cannot handle the entire problem thus making the decomposition necessary.

2 Problem deﬁnition and notation

2.1 Problem deﬁnition

Let Ibe the set of nodes of an intermodal network. Subset J⊂Iincludes the Distribution Centers hubs (DC

hubs), in which orders Nare consolidated into loading compartments G. Each compartment is dedicated to one

DC hub, hence set Gis divided into subsets Gj, j ∈J. Subset L⊂Iincludes Satellite hubs, in which orders are

brought to before their ﬁnal destination. The rest of the nodes of set I, namely intermediate hubs, are labelled

as K⊂I.

After the completion of the consolidation process, all loaded compartments must be shipped to any Satellite

hub l∈L, via an intermodal services network. We consider three transport modes (i.e., roadway, railway, and

seaway modes) and a set of scheduled transport services, denoted by S. Each service s∈Sis featured with an

origin node origins∈I, a destination node dests∈I, a ﬁxed time of departure and arrival (departuresand

arrivalsrespectively), a variable cost ctravel

s, which is charged for each compartment that is shipped by service

s, a ﬁxed cost cf ixed

s, and a capacity (in number of compartments) Qs. For each node i∈I, we distinguish

the services arriving in and departing from it, by introducing the sets δ−(i) and δ+(i), respectively. Last, each

service is linked with a subset of invalid co-assignments Fs⊂S, that is the set of services that cannot be added

in the same intermodal route with s. Each subset Fsincludes all services p∈S\ {s}that:

a. depart or arrive during service s(i.e., departures≤departurep< arrivalsor departures< arrivalp≤

arrivals),

b. start from the destination of sbefore the completion of s(i.e., originp=destsand departurep< arrivals),

c. arrive to the origin of slater than the departure of s(i.e., destp=originsand arrivalp> departures).

The solution of the intermodal transportation stage is a set of combined services, that start from a DC hub and

terminate to a Satellite hub. Each service is linked with a set of assigned compartments. Note that, despite the

dedication of each order or compartment to a DC hub, there are no pre-assignments to Satellite hubs, hence each

loaded compartment could be transferred to any Satellite hub by eligible services, regardless of its components.

As the problem requires the assignment of loaded compartments to services of diﬀerent capacity and cost,

the intermodal transportation stage is structured as a Generalized Assignment Problem, which is known to be

NP-hard [13]. The complexity arises from orders being loaded to compartments, which must then be transferred

through the intermodal network at a minimum ‘ﬂow’ cost.

Concerning now the last-mile stage, each order n∈Nis featured with a deadline tnand a value of weight

wn, which is related with the importance of the order. The deadlines are not strict, nevertheless their violation

implies a penalty cost, equal with the number of days of delayed delivery, multiplied by the weight value of the

order. To comply with the properties of hub-and-spoke networks, in which all orders are delivered in a single

route, we consider a TSP for each used service s∈ {S|destinations∈L}, starting from dests∈Land traversing

through the delivery points of all orders that were shipped by service s.

As the objective function of each TSP includes the total transportation costs and the delay penalties, the

last-mile stage is structured as a set of multiple Single-Machine Scheduling Problems with sequence-dependent

times, aiming to minimize the total weighted tardiness, which are known to be strongly NP-hard [23].

An illustrative example of the intermodal network, the available services that connect the hubs, and the

processes that are conducted in each stage of the problem is presented in Figure 1.

Figure 1: A sketch of our network

2.2 Mathematical Model

Let Pbe an MILP formulation for the uniﬁed optimization problem that was described above. Parameters and

variables of Pare as in Table 2.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Logic-BasedBendersforintermodaloperationswithdelaypenaltiesIoannisAvgerinos1,*,IoannisMourtos1,andGeorgiosZois11ELTRUNLab,DepartmentofManagementScienceandTechnology,AthensUniversityofEconomicsandBusiness,Patision76,10434,Athens,GreeceE-mail:iavgerinos@aueb.gr,mourtos@aueb.gr,georzois@aueb.gr*Corresp...

展开>> 收起<<

Logic-Based Benders for intermodal operations with delay penalties Ioannis Avgerinos1 Ioannis Mourtos1 and Georgios Zois1 1ELTRUN Lab Department of Management Science and Technology Athens University of Economics and Business.pdf

共26页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Logic-Based Benders for intermodal operations with delay penalties Ioannis Avgerinos1 Ioannis Mourtos1 and Georgios Zois1 1ELTRUN Lab Department of Management Science and Technology Athens University of Economics and Business

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: