Model and algorithm for bilevel multisized terminal location‐routing problem for the last mile delivery

• Date: 01 January 2019
• DOI: http://doi.org/10.1111/itor.12399
• Published date: 01 January 2019

Intl. Trans. in Op. Res. 26 (2019) 131–156

DOI: 10.1111/itor.12399

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Model and algorithm for bilevel multisized terminal

location-routing problem for the last mile delivery

Lin Zhoua,b, Yun Linb, Xu Wangband Fuli Zhoub

aCollege of Management, Chongqing University of Technology, Chongqing, China

bCollege of Mechanical Engineering, Chongqing University, Chongqing, China

E-mail: zhoulin1205@126.com [L. Zhou]; linyun313@163.com [Lin]; wx921@163.com [Wang];

fl.zhou@cqu.edu.cn [F. Zhou]

Received 17 May2015; received in revised form 9 October 2016; accepted 18 January 2017

Abstract

The last mile delivery is regarded as one of the most expensive but least efficient stretches in the business-

to-customer supply chain. Designing the last mile delivery system in a lean way is crucial to serve customers

efficiently and economically. To address this issue, we propose a bilevel multisized terminal location-routing

problem (BL-MSTLRP) with simultaneous home delivery and customer’s pickup services. The solution

method is proposed by combining genetic algorithm (GA) and simulatedannealing (SA), called self-adaptive

SGA. Studies for designing the last mile deliverysystem in a real-world environment indicate the validityof the

proposed model based on the comparison of different scenarios. Numerical experiments are also conducted

to evaluate the performance of the presented SGA. Computational results show that the hybrid approach

efficiently solves the BL-MSTLRP.

Keywords: Last mile delivery; bilevel location-routing problem; multisized terminal; genetic algorithm; simulated

annealing

1. Introduction

Recently, e-commerce has become widely accepted and the growing interest is causing a sustainable

boom. According to JP Morgan’s annual Internet Investment Guide, the annual growth rate of

e-commerce sales is approximately 20% (Hayel et al., 2016). The sharply developing e-commerce

market has driven explosive growth in logistics demand. The last mile delivery, working as the

last stage in delivering parcels to final customers, plays an indispensable role in promoting e-

commerce development. A survey showed that 85% of buyers who received their orders on time

would repurchase online compared with 33% whose orders were received late (Esper et al., 2003).

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

132 L. Zhou et al. / Intl. Trans. in Op. Res. 26 (2019) 131–156

Unlike traditional city distribution, considerable numbers of customers with small daily delivery

demands are widely spatially distributed under e-commerce. Moreover, customers vary in times of

availability due to various occupations, which makes the last mile delivery the most expensive but

least efficient part of the e-commerce supply chain. According to the survey, the last mile delivery

cost accounts for 13% up to 75% of the total supply chain cost (Aized and Srai, 2014). Thus, the

key issue of the last mile delivery is to efficiently design the last mile delivery system (Agatz et al.,

2008).

Individual direct parcel delivery to customers’ home or work (home delivery, HD) is time-

consuming and costing. Moreover, the logistics operators’ delivery schedules usually cause passive

parcel receipt for the customers. Subsequently, another service has been widely accepted by both

the logistics operators and customers, namely, customer’s pickup (CP). More precisely, CP service

means customers pick up their parcels at a facility (referred as a terminal) that is close to their

home or work (Hayel et al., 2016). Instead of delivering all parcels to customers’ home or work

individually, by providing CP service, certain parcels could be delivered to terminals in larger

lot sizes, the efficiency therefore would be improved, and economies of scale could be achieved.

For customers, it would be preferable to pick up and deliver parcels based on their individual

timetables.

The two optional services providedin last mile delivery system enable customers to make decisions

based on their requirements, particularly the distance to the terminals. Within short distances, the

number of customers opting for CP service increase, therefore fixed vehicle and routing costs may

decrease accordingly. However, the increasing density of opened terminals may inevitably increase

the terminal operation costs, and vice versa. Hence, terminal location and vehicle routing are two

interrelated major concerns in last mile delivery system. In urban area, especially in the city center,

the scarcity of available land causes high cost sensitivity to terminal size selection when choosing the

location. In addition, as vehicles would deliver parcels to the terminals in relatively large lot sizes

and to individual customers in single parcel as well, the ability to schedule vehicles with multiple

types may help to improve comprehensive utilization. Therefore, appropriate strategies and lean

operations should be considered to guarantee efficient and economical parcel delivery to customers

when designing the last mile delivery system.

This paper proposes a novelbilevel multisized terminal location-routing problem (BL-MSTLRP)

for the last mile delivery under the e-commerce environment. The two levelsof routes are connected

based on customers’ service options. For the first level, vehicles deliver parcelsfrom the distribution

center (DC) to the selected terminals; and for the second level, vehicles also deliverparcels by way of

the DC but directly to individualcustomers. A comprehensive bilevel location-routingmathematical

model is then developed for this problemsimultaneously considering HD and CP services, terminal

sizes, and vehicle types. The objective is to minimize the total delivery cost, including fixed and

variable cost. To solve the model, self-adaptive SGA is designed by combining genetic algorithm

(GA) with simulated annealing (SA).

The remainder of this paper is organized as follows. Section 2 reviews the relevant literature

on the Last Mile under business-to-customer (B2C) and LRPs. Problem description, notions, and

the quantitative model are displayed in Section 3. Section 4 presents the proposed SGA heuristic

for solving the BL-MSTLRP. Numerical experiments are developed to study the performance of

the proposed model and designed algorithm in Section 5. Finally, conclusions and possible future

research directions are given in Section 6.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies