Multi-purpose Pickup and Delivery Problem for Combined Passenger and Freight Transport

2025-04-24 0 0 2.79MB 27 页 10玖币

侵权投诉

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

Multi-purpose Pickup and Delivery Problem for Combined Passenger and

Freight Transport

Jonas Hatzenb¨uhler1,∗

, Erik Jenelius1, Gy˝oz˝o Gid´ofalvi2, Oded Cats1,3

KTH Royal Institute of Technology, 100 44 Stockholm, Sweden

Abstract

Recent developments in modular transport vehicles allow deploying multi-purpose vehicles which can alternately

transport diﬀerent kinds of ﬂows. In this study, we propose a novel variant of the pickup and delivery problem, the

multi-purpose pickup and delivery problem, where multi-purpose vehicles are assigned to serve a multi-commodity

ﬂow. We solve a series of use case scenarios using an exact optimization algorithm and an adaptive large neighborhood

search algorithm. We compare the performance of a multi-purpose vehicle ﬂeet to a mixed single-use vehicle ﬂeet.

Our ﬁndings suggest that total costs can be reduced by an average of 13% when multi-purpose vehicles are deployed,

while at the same time reducing the total vehicle trip duration and total distance travelled by an average of 33% and

16%, respectively. The size of the ﬂeet can be reduced by an average of 35%. The results can be used by practitioners

and policymakers to decide on whether the combination of passenger and freight demand ﬂows with multi-purpose

vehicles in a given system will yield beneﬁts compared to existing ﬂeet conﬁgurations.

Highlights:

•formulating and solving a novel multi-purpose pickup and delivery problem

•analysis of urban scenarios with varied spatial and temporal demand

•cost savings by an average of 13%

•reduction of ﬂeet size by an average of 35%

•reduction of total vehicle trip duration by an average of 33%

•reduction of total distance travelled by an average of 16%

Keywords: Public transportation, Freight transportation, Multi-purpose vehicles, Heuristic optimization

1. Introduction

The ongoing trends of urbanization, increasing e-shopping, and digitalization of supply chain management challenge

the eﬃciency and sustainability of the existing transportation systems. Savelsbergh and Woensel (2016) and Los et al.

(2020) stress the importance of integrated and/or collaborative transportation solutions to achieve eﬃciency and sus-

tainability. The authors speciﬁcally address the concept of utilizing vehicle capacities for multiple purposes.

Public transportation and urban freight delivery operations are conventionally designed as two independent systems.

Public transportation systems are designed to satisfy the passenger demand peaks (Ceder and Wilson, 1986), while

logistic operations are designed to meet delivery times (Ghilas et al., 2016b). In oﬀ-peak periods public transportation

∗Corresponding author:

Email address: jonashat@kth.se (Jonas Hatzenb¨uhler)

1Division of Transportation Planning, KTH Stockholm, Sweden

2Department of Urban Planning and Environment, KTH Stockholm, Sweden

3Department of Transport and Planning, Delft University of Technology, Netherlands

Preprint submitted to EURO Journal on Transportation and Logistics Submitted: June, 2022

may experience unused vehicle capacity and empty-vehicle kilometers, while the urban logistics during the same

periods are dominated by daily goods and parcel deliveries between stores, warehouses, and companies. For traﬃc

safety reasons and maneuverability in urban environments, these vehicles are typically small or medium-sized trucks.

However, both transportation systems strive to eﬃciently satisfy the transportation needs of requests (i.e., passenger

or freight items) at a speciﬁc time to a speciﬁc destination.

The concept of combining multiple demand ﬂows in one transport system is known as integrated transportation.

In the past, several projects have investigated and demonstrated the successful integration of passenger and freight

transportation in urban environments. In Amsterdam, Netherlands (Marinov et al., 2013) a pilot project investigated

the delivery of consumer goods in specially designed trams that operate in between the passenger trams. The trams

transported goods from a suburban depot to a shopping mall in the city center. The integration of ﬂows was achieved

by sharing the same track network and infrastructure. The service was operating from 2007-2009 but had to be

terminated due to missing political and ﬁnancial support since the operations could not be realized without subsidies.

A vehicle production plant in Dresden, Germany (Mueller-Eberstein and Franke, 2000) was supplied by a tram. The

tram operates during oﬀ-peak hours and uses the same tracks as the passenger tram. The tram has only two stops, at

the production plant and at the logistic center. The operations in Dresden were terminated in the beginning of 2021

after 19 years of operations. The reason for this was a changed logistic concept for the new vehicle produced in the

factory, which fully utilized delivery trucks.

The consolidation of multiple demand ﬂows in one transport system can be realized in diﬀerent ways. Mourad et al.

(2019) present a survey of models and algorithms for optimizing the shared transportation of passenger and freight

items.

One concept for integrating multiple item types is sequential integration. In this concept, diﬀerent types of items are

transported by the same vehicle but at diﬀerent times. SteadieSeiﬁ et al. (2014), Cochrane et al. (2017), Ozturk and Patrick

(2018), Behiri et al. (2018) and Li et al. (2021) propose diﬀerent modes of operation and give examples of successful

integration. This concept is typically applied to rail-bound transportation modes like the tram, metro, or train systems

or to systems combining ﬁxed-line services with on-demand services. In Mourad et al. (2020) the authors propose a

variant of the PDP with simultaneous integration. Small pickup and delivery robots are integrated into scheduled line

services. The robots can then be used to directly serve certain requests in a local area or travel in the scheduled line

to reach other requests. The authors show that this integrated approach can lead to 18.2% cost savings compared to

a pure freight system. Compared to simultaneous integration concepts, sequential integration requires to physically

adjust the vehicle for each item type. However, the combined optimization of multiple item types may still lead to an

overall improved system as compared to the independent operation of single-purpose ﬂeets. Additionally, for sequen-

tial integration of multiple item types, passenger requests are not mixed with e.g. freight items, which guarantees that

passenger requests are not aﬀected by the delivery and pickup of freight items. For simultaneous integration concepts,

freight requests would be mixed with passenger requests which would lead to additional stops for the vehicles, which

in turn reduce the level of service for the passengers in this vehicle. Another advantage of sequential integration is

the higher capacity for each demand type when exclusively served, which brings greater ﬂexibility for which freight

items can be delivered.

The eﬃcient operation of multiple vehicles is ﬁrst already envisioned and described in Dantzig and Ramser (1959) as

the truck dispatching problem. Since then numerous variations, extensions, and solution algorithms have been devel-

oped (see Toth and Vigo (2014); Koc¸ et al. (2016); D¨undar et al. (2021) for recent comprehensive literature reviews).

Two of the most studied variations are the Pickup and Delivery Problem (PDP), where a request has a pickup position

and a delivery position, and the more general Dial-a-ride Problem (DARP), in which dynamic requests are served (see

Desrochers et al. (1988), Savelsbergh and Sol (1995) for the PDP, and Cordeau and Laporte (2007), Berbeglia et al.

(2010) for the DARP).

In this study, we revise the pickup and delivery problem formulation to facilitate the operation of multi-purpose

vehicles, i.e. the Multi-Purpose Pickup and Delivery Problem (MP-PDP). We analyze in a series of experiments

the potential beneﬁts this vehicle concept has over conventional transportation systems. The proposed problem is a

variation of the heterogeneous routing problem (see Koc¸ et al. (2016)) and the truck-and-trailer routing problem (see

Derigs et al. (2013)). The main variation in comparison to these problems is the change of vehicle type during a

(a) Scania NXT vehicle concept (Scania, 2020) (b) U-Shift vehicle concept (DLR, 2021)

Figure 1: Illustration of the multi-purpose vehicle concept

vehicle trip. Additionally, the module can be changed between several vehicle platforms at several places, whereas

at the truck-and-trailer routing problem, the trailer is dropped and connected to the truck at the same dedicated place.

In the following, we study the operation of sequential deliveries of freight and passengers between origins (pickup

locations) and destinations (drop oﬀlocations). Hence, our work also extends the sequential integration concepts

for road network-based operations by adding the concept of modularity and vehicle module handling to the problem

formulation.

The operation can be explained as follows: A vehicle operates on a route that starts and ends at a depot. A vehicle can

either deliver goods from the depot to a set of customers or transport passengers from their origins to their destinations.

A vehicle is modeled as consisting of two parts. The ﬁrst part is the platform, which contains steering, engine,

and wheels. The second part is a functional module that determines the purpose of the vehicle - either passenger

transportation or freight delivery. The module can be exchanged at a depot or a special service depot, and thus change

the purpose of the vehicle (see Figure 1).In the proposed problem two diﬀerent modules can be used, one exclusively

for passenger transport (bus/ride-pooling operations) and the other for the exclusive delivery of freight items (freight

truck operation).

The contribution of this paper is threefold. First, the work addresses the research gap of sequentially integrated

transportation systems for passenger and freight transportation on road networks. Second, the proposed problem

formulation extends the existing research on PDP by separating the assignment of platforms and modules to requests,

which allows the modelling of multiple changing processes at diﬀerent locations throughout a single route. For these

problem-speciﬁc model characteristics additional heuristics are implemented. Third, the paper studies the impact of

multi-purpose vehicles through analyzing various large-scale scenarios.

The remainder of the paper is structured as follows. First, the relevant literature is reviewed in Section 2. Then

the problem formulation and methodology of this study are described in Section 3. The experimental design and the

results are discussed in Section 4 and Section 5, respectively. The paper closes with a critical assessment of the results,

a conclusion, and an outlook for potential future studies in Section 6.

2. Literature Review

The vehicle routing problem (VRP) has been widely studied for several decades and many variations in problem for-

mulation and solution algorithms have been developed. Among the latest developments are four problem formulations

relevant to the proposed formulation in this work: ﬁrst, the heterogeneous vehicle routing problem as comprehensively

reviewed by Koc¸ et al. (2016); second, the swap body vehicle routing problem (VeRoLog, 2014); third, the trailers

and transshipment vehicle routing problem (Drexl, 2013); and fourth, the share-a-ride problems. We elaborate on the

relation between the problem addressed in this study and each of those in the subsequent paragraphs.

The heterogeneous routing problems describe logistic/routing operations with diﬀerent types of demand and demand

type speciﬁc vehicles to serve that demand. A common practical application of this routing problem is found in health-

care transport. In Parragh (2011) and Parragh et al. (2012) the authors describe a DARP with heterogeneous demand

and vehicles for the transportation of patients and disabled people. In their model vehicles may be equipped with staﬀ

seats, patient seats, stretchers and wheelchair places which in turn deﬁne the demand type and capacity for each vehi-

cle. Another form of heterogeneous routing problems is considered by Rekiek et al. (2006) and Melachrinoudis et al.

(2007) where diﬀerent vehicles in terms of capacity are utilized to serve a single type of demand. This problem is

closely related to mixed vehicle routing problems, which do not consider pickup and drop oﬀpositions for each re-

quest. In comparison to these heterogeneous routing problems the model proposed in this work allows for an en-route

change in vehicle conﬁguration. In the previously studied heterogeneous routing problems, the vehicle conﬁguration is

decided upon before the depot departure and remains the same until the vehicle returns to the depot. Additionally, the

number of conﬁguration changes is not limited, allowing for several conﬁgurations for a given route. In Qu and Bard

and Tellez et al. the authors present heterogeneous PDP and DARP with conﬁgurable vehicles, respectively. In these

works vehicles can reconﬁgure their interior and, by that, change the capacity of the vehicle. The others propose a

mixed-integer program which is solved using an ALNS in both papers. In Qu and Bard the authors analyze several

scenarios and conclude that cost savings of 30%-40% can be achieved by changing the conﬁguration of the vehicles.

The Swap Body Vehicle Routing Problem (SB-VRP) was introduced as part of an operations research computation

challenge and has been solved by several research teams, for example (Huber and Geiger, 2017; Todosijevi´c et al.,

2017; Toﬀolo et al., 2018). In essence, the problem considers the routing of trucks, which can attach or remove

trailers of a certain length. The nature of this problem is similar to the here proposed MP-PDP. However, in the SB-

VRP the start and end depot for a trailer has to be one and the same, whereas in the MP-PDP a module can be loaded

and dropped at any depot or service depot, hence embracing a more general and ﬂexible functionality. Furthermore,

no multi-depot functionality is implemented in the original problem formulation. Additionally, the SB-VRP can deal

with two diﬀerent types/sizes of trailers whereas the proposed work here can be easily extended to consider more

vehicle types, e.g. passenger, freight, and waste transportation. Finally, the proposed vehicle routing problem extends

the SB-VRP by adding additional constraints, such as maximum range per platform.

The third group of related vehicle routing problems are the trailer and transshipment problems (Drexl, 2013). In

addition to an adjusted objective function formulation, several additional constraints capturing the multi-depot con-

siderations in the proposed MP-PDP formulation create a new problem variant. In truck-and-trailer routing problems

only freight demand is typically considered (Derigs et al. (2013) and Parragh and Cordeau (2017)). Moreover, the

types of trailer are limited to one; hence, only the addition or removal of trailers is considered. In contrast, the MP-

PDP allows for the investigation of several demand type-speciﬁc modules, each of which having a diﬀerent capacity.

Li et al. (2014) investigate if another mode of passenger transportation, namely private taxi rides, can be used for

integrated urban transportation. The authors propose a reduced version of the Share-a-Ride problem and the Freight

Insertion problem. The problem minimizes the additional operating costs of adding freight items in a set of planned

taxi trips. The authors solve their proposed mixed-integer linear program (MILP) for static and dynamic demand

scenarios. The numerical results are sensitive to the spatial distribution of the freight demand. The authors conclude

that the integration of freight items into taxi services is a promising solution for urban areas. However, this new

integrated mode should be complemented by a traditional truck service to guarantee the delivery of all packages.

Schr¨oder and Liedtke (2017) present a multi-agent simulation model for passenger and freight transportation. They

investigate the impacts of various policy measures, i.e. special vehicle tolls.

Since the computational complexity of vehicle routing and scheduling problems has proven to be NP-hard (Lenstra and Kan,

1981), it is challenging to eﬃciently solve these problems for larger scenarios. Two general approaches are typically

used to solve the VRP and its variations: (i) the utilization of exact analytical algorithms (e.g. Branch-and-Cut,

Branch-and-Bound) and, (ii) the development of problem-speciﬁc heuristics or meta-heuristic algorithms (e.g. Sim-

ulated Annealing, Artiﬁcial Bee Colony, Genetic Algorithm or Large Neighborhood Search). In Arslan et al. (2016)

a crowd-sourced delivery system for parcels and passengers is solved using an exact solution approach. An exact

algorithm for the shared ride problem is presented by Beirigo et al. (2018), while Ghilas et al. (2016b) solve the PDP

with time windows and scheduled lines using CPLEX.

Due to the computational complexity of VRP problems, most researchers implement heuristic algorithms to solve large

problems. Chew et al. (2013) develop a bi-objective genetic algorithm (GA) for the VRP and show its ability to reach

improved objective values over previously published algorithms for Mandl’s benchmark problems. Alizadeh Foroutan et al.

(2020) apply a similar genetic algorithm as well as simulated annealing (SA) algorithm to the green routing prob-

lem. The authors show that GA converges faster, whereas SA results in better solution robustness and qualities. In

Ropke and Pisinger (2006) the adaptive large neighborhood search algorithm (ALNS) is presented. It is shown that the

ALNS improves the best known solutions for VRP problems by around 50%. Additional computational experiments

indicate convergence robustness and its adaptability to various variations in problems. These results are conﬁrmed in

a later study by Pisinger and Røpke (2010) which shows that large-scale neighborhood search methods lead to fast

and robust convergence for complex combinatorial problems. The authors propose variable local search algorithms

and adaptive neighborhood deﬁnitions to further improve the computational eﬃciency of the algorithm. In the works

of Masson et al. (2013), Ghilas et al. (2016a) and Li et al. (2016) the authors apply the ALNS to a variation of the

VRPs. In their works, the authors solve the various VRPs by developing problem-speciﬁc heuristics.

Based on the review of the literature, we conclude that in recent years the integration and combination of multiple

demand types in diﬀerent transportation modes have been investigated. The beneﬁts of which could be shown for

simultaneous combination problems. Several authors proposed novel meta-/heuristic algorithms to solve complex

VRP problems and showed their superiority in computation time and objective value over exact algorithms. Therefore,

we have used a meta-heuristic optimization algorithm to solve the novel MP-PDP.

3. Methodology

The main characteristics of the pickup and delivery problem as proposed in this work are the multi-purpose vehicle

concept and the optimal consolidation of passenger and freight items. In this section, the detailed problem formulation

and solution algorithm are given.

3.1. Proof of Concept

In Figure 2 a simple routing example is given. This example showcases the theoretical beneﬁts of multi-purpose

vehicles over conventional vehicles. Figure 2a shows the conventional case. This solution is optimal and utilizes

two vehicles (blue and red), one serving the freight requests, while the second vehicle serves the passenger requests.

Therefore, this solution uses two platforms and two modules to serve the requests. In Figure 2b the same demand is

served on a single route (blue). This solution utilizes the additional service depot to change the module and hence the

purpose of that vehicle. Therefore, this solution uses one platform and two modules. The number of platforms could

be reduced at the cost of exchanging modules once. Additionally, the total vehicle operation time is reduced from

20min +20min +30min +30min +40min +20min +30min =190min to 20min +20min +30min +10min +10min +

20min +30min =140min.

(a) Routing solution with conventional vehicles (b) Routing solution with multi-purpose vehicles

Figure 2: An illustration of conventional vehicle operations and multi-purpose vehicle operations

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

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

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.05700v1[math.OC]11Oct2022Multi-purposePickupandDeliveryProblemforCombinedPassengerandFreightTransportJonasHatzenb¨uhler1,∗,ErikJenelius1,Gy˝oz˝oGid´ofalvi2,OdedCats1,3KTHRoyalInstituteofTechnology,10044Stockholm,SwedenAbstractRecentdevelopmentsinmodulartransportvehiclesallowdeployingmulti...

展开>> 收起<<

Multi-purpose Pickup and Delivery Problem for Combined Passenger and Freight Transport.pdf

共27页,预览5页

还剩页未读，继续阅读

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

Multi-purpose Pickup and Delivery Problem for Combined Passenger and Freight Transport

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: