A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics

Published on Jul 1, 2020in Transportation Research Part A-policy and Practice5.594
· DOI :10.1016/J.TRA.2018.10.033
Nicolas Rincon-Garcia2
Estimated H-index: 2
 (Pontifical Xavierian University), Ben Waterson12
Estimated H-index: 12
 (University of Southampton)+ 1 AuthorsFernando Salazar-Arrieta1
Estimated H-index: 1
 (Pontifical Xavierian University)
Sources
Abstract
Abstract New retail trends show the increasing importance of providing cost efficient deliveries in cities, where congestion and compliance with driving hours regulations should be incorporated into routing software. This paper introduces a large neighbourhood search algorithm that substantially improves the benchmark solutions (in terms of the number of vehicles required, travel distance and duty time) for the vehicle routing problem variant considering time windows, time-dependent travel times and driving hours regulations (EC) 561/2006 that apply to vehicles over 3.5 tons in European cities. Additionally, instances for The Road Transport (Working Time) Regulation 2005 that applies to drivers in the United Kingdom are introduced. The proposed algorithm is also used in scenarios that represent home delivery conditions to evaluate the impacts of the length of time windows, customer density, congestion and regulations in terms of cost and environmental impact.
Figures & Tables
Download
📖 Papers frequently viewed together
20124.96Production and Operations Management
3 Authors (Ola Jabali, ..., de Ag Ton Kok)
2014
3 Authors (Qiang Li, ..., Lixin Miao)
20165.60Transportation Research Part B-methodological
2 Authors (Gonçalo Homem de Almeida Correia, Bart van Arem)
References41
Newest
Dec 1, 2017·Computers & Operations Research4.01
#1Agustín Montero (UBA: University of Buenos Aires)H-Index: 3
#2Isabel Méndez-Díaz (UBA: University of Buenos Aires)H-Index: 12
Last. Juan José Miranda-Bront (UBA: University of Buenos Aires)H-Index: 6
view all 3 authors...
Abstract Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where the travel times are not assumed to be constant along the day. The motivation to consider the time dependency factor is that it enables to have better approximations to many problems arising ...
Source
Abstract Although the Vehicle Routing Problem (VRP) has been broadly addressed in the literature, most of the works consider constant travel times. This is a strong simplification that does not allow to correctly model real world applications. In fact, nowadays, travel times sensibly change, across the day, due to congestion phenomena. Therefore, to actually represent the reality, it is necessary to consider time dependent travel times. In this paper, the VRP with Time Dependent Travel Times, se...
Source
Mar 1, 2017·EURO Journal on Transportation and Logistics
#1Diego Cattaruzza (ENSMP: Mines ParisTech)H-Index: 10
#2Nabil Absi (ENSMP: Mines ParisTech)H-Index: 22
Last. Jesus Gonzalez-Feliu (ENSMP: Mines ParisTech)H-Index: 27
view all 4 authors...
This paper surveys the vehicle routing problems met in cities for good distribution. It applies the following methodology. First, it gives an overview of the literature devoted to vehicle route optimization in cities. Then, it classifies and analyses urban logistic flows. As a result, it identifies the principal scientific challenges that need to be addressed: time-dependency, multi-level and multi-trip organization of the distribution, dynamic information. Finally, it focuses on each one of the...
Source
This article paper presents a hybrid metaheuristic algorithm to solve the time-dependent vehicle routing problem with hard time windows. Time-dependent travel times are influenced by different congestion levels experienced throughout the day. Vehicle scheduling without consideration of congestion might lead to underestimation of travel times and consequently missed deliveries. The algorithm presented in this paper makes use of Large Neighbourhood Search approaches and Variable Neighbourhood Sear...
Source
May 1, 2016·Transportation Science4.12
#1Xinan YangH-Index: 6
#2Arne K. Strauss (Warw.: University of Warwick)H-Index: 11
Last. Richard W. EgleseH-Index: 29
view all 4 authors...
Attended home delivery services face the challenge of providing narrow delivery time slots to ensure customer satisfaction, while keeping the significant delivery costs under control. To that end, a firm can try to influence customers when they are booking their delivery time slot so as to steer them toward choosing slots that are expected to result in cost-effective schedules. We estimate a multinomial logit customer choice model from historic booking data and demonstrate that this can be calib...
Source
Dec 1, 2015·Computers & Operations Research4.01
#1Michel Gendreau (École Polytechnique de Montréal)H-Index: 99
#2Gianpaolo GhianiH-Index: 27
Last. Emanuela GuerrieroH-Index: 13
view all 3 authors...
Time-dependent routing amounts to design "best" routes in a graph in which arc traversal times may vary over the planning horizon. In the last decade, a number of technological advances have stimulated an increased interest in this field. We survey the research in the area and present a comprehensive review of travel time modelling, applications and solution methods. In particular, we make a first classification in point-to-point and multiple-point problems. A second major classification is then...
Source
Aug 1, 2014·Transportation Science4.12
#1Asvin Goel (Kühne Logistics University)H-Index: 17
#2Thibaut VidalH-Index: 28
Driver fatigue is internationally recognized as a significant factor in approximately 15%--20% of commercial road transport crashes. In their efforts to increase road safety and improve working conditions of truck drivers, governments worldwide are enforcing stricter limits on the amount of working and driving time without rest. This paper describes an effective optimization algorithm for minimizing transportation costs for a fleet of vehicles considering business hours of customers and hours of...
Source
May 1, 2014·European Journal of Operational Research5.33
#1Thibaut Vidal (UdeM: Université de Montréal)H-Index: 28
#2Teodor Gabriel Crainic ('ENS Paris': École Normale Supérieure)H-Index: 76
Last. Christian Prins (Team Losi)H-Index: 58
view all 4 authors...
Vehicle routing attributes are extra characteristics and decisions that complement the academic problem formulations and aim to properly account for real-life application needs. Hundreds of methods have been introduced in recent years for specific attributes, but the development of a single, general-purpose algorithm, which is both efficient and applicable to a wide family of variants remains a considerable challenge. Yet, such a development is critical for understanding the proper impact of att...
Source
Mar 20, 2014·Procedia - Social and Behavioral Sciences
#1Johan Visser (TU Delft: Delft University of Technology)H-Index: 12
#2Toshinori Nemoto (Hitotsubashi University)H-Index: 11
Last. Michael Browne (University of Westminster)H-Index: 39
view all 3 authors...
This review paper discusses the latest developments in internet shopping, home delivery and the potential impacts on city logistics and alternative vehicle use. The review has illustrated the rapid changes during the past few years and the potentially important impacts on patterns of transport within urban areas. Some of the changes result in increased pressure for road traffic networks in sensitive areas (for example residential areas). At the same time the changes also provide opportunities fo...
Source
Jan 1, 2014·Transportation research procedia
#1Simona Mancini (Polytechnic University of Turin)H-Index: 20
Vehicle routing and scheduling play a crucial role in the distribution chain. Although this research area has been broadly studied in the literature, there is still a lack of models closely representing real life problems. Most of the models proposed address constant travel times between nodes, without taking into account rush hours traffic congestion. In real applications in urban contexts the increasing of travel times due to congestion effects cannot be neglected. Models dealing with time dep...
Source
12345
Cited By14
Newest
Nov 30, 2021·Expert Systems With Applications6.95
#1Wenheng Liu (UTBM: Universite de technologie de Belfort-Montbeliard)H-Index: 1
#2Mahjoub Dridi (UTBM: Universite de technologie de Belfort-Montbeliard)H-Index: 11
Last. Amir Hajjam El Hassani (UTBM: Universite de technologie de Belfort-Montbeliard)H-Index: 8
view all 4 authors...
Abstract null null The home health care routing and scheduling problem (HHCRSP), a challenging operational problem in the field of home health care (HHC), consists of assigning suitable caregivers to serve patients at their homes and optimizing a set of caregiver’s visits according to certain criteria. Besides the time windows and qualifications of caregivers that are generally considered in HHCRSP, this study further concerns three practical constraints, which are (1): some patients require the...
Source
Sep 23, 2021·European Journal of Operational Research5.33
#1Faycal A. Touzout (INSA Lyon: Institut national des sciences Appliquées de Lyon)H-Index: 4
#2Anne-Laure Ladier (INSA Lyon: Institut national des sciences Appliquées de Lyon)H-Index: 7
Last. Khaled Hadj-Hamou (INSA Lyon: Institut national des sciences Appliquées de Lyon)H-Index: 9
view all 3 authors...
Abstract null null In this paper, we consider a variant of the Inventory Routing Problem (IRP), the Time-Dependent IRP (TD-IRP). The TD-IRP extends the routing component of the IRP by making the travelling time between two locations no longer constant but depending on the departure time. In order to investigate the relevance of considering time-dependent travelling time functions, a set of new benchmark instances based on real-data is assumed. Numerical experiments show that optimising with time...
Source
#1Dhirendra PrajapatiH-Index: 3
#2M. Manoj Kumar
Last. Mohd Zuhair
view all 5 authors...
In the recent era, the rapidly increasing trend of e-commerce business creates opportunities for logistics service providers to grow globally. With this growth, the concern regarding the implementation of sustainability in logistic networks has received attention in recent years. Thus, in this work, we have focused on the vehicle routing problem (VRP) to deliver the products in a lesser time horizon with driver safety concern considerations in business (B2B) e-commerce platforms. We proposed a s...
Source
The e-commerce market in cities is currently one of the fastest-growing markets By observing the current changes taking place in it, we have a unique opportunity to learn about its potential development directions in the future with great acceleration Some of the recent changes caused by the ongoing COVID-19 pandemic have a chance to affect this market's development in the coming years permanently The paper's primary purpose is to identify relationships between factors that could significantly i...
Source
#1Vincent F. YuH-Index: 2
#2WinarnoH-Index: 1
Last. Chao-Lung YangH-Index: 7
view all 6 authors...
This research presents a variant of the vehicle routing problem known as the path cover problem with time windows (PCPTW), in which each vehicle starts with a particular customer and finishes its route at another customer. The vehicles serve each customer within the customer’s time windows. PCPTW is motivated by a practical strategy for companies to reduce operational cost by hiring freelance workers, thus allowing workers to directly service customers without reporting to the office. A mathemat...
Source
May 1, 2021·Computers, Environment and Urban Systems5.32
#1Tomislav Erdelic (University of Zagreb)H-Index: 5
#2Tonči Carić (University of Zagreb)H-Index: 7
Last. Niko Jelušić (University of Zagreb)H-Index: 4
view all 6 authors...
Abstract Efficiently predicting traffic congestion benefits various traffic stakeholders, from regular commuters and logistic operators to urban planners and responsible authorities. This study aims to give a high-quality estimation of traffic conditions from a large historical Floating Car Data (FCD) with two main goals: (i) estimation of congestion zones on a large road network, and (ii) estimation of travel times within congestion zones in the form of the time-varying Travel Time Indexes (TTI...
Source
#1Kim J. Los
#2Frank Phillipson (TNO: Netherlands Organisation for Applied Scientific Research)H-Index: 7
Last. Uilke Stelwagen
view all 5 authors...
Offering time windows to receivers of last-mile delivery is becoming a distinguishing factor. However, we see that in practice carriers have to create routes for their vehicles based on destination information, that is just being revealed when a parcel arrives in the depot. The parcel has to be assigned directly to a vehicle, making this a Dynamic Assignment Vehicle Routing Problem. Incorporating time windows is hard in this case. In this paper an approach is presented to solve this problem incl...
Source
Sep 18, 2020·Energies3.00
#1Ryszard K. MilerH-Index: 4
#2Marcin J. KisielewskiH-Index: 1
Last. Antonina KalinichenkoH-Index: 8
view all 4 authors...
Implemented in road transport enterprises (RTEs) on a large scale, telematics systems are dedicated both to the particular aspects of their operation and to the integrated fields of the total operational functioning of such entities. Hence, a research problem can be defined as the identification of their efficiency levels in the context of operational activities undertaken by RTEs (including more holistic effects, e.g., lowering fuel/energy consumption and negative environmental impacts). Curren...
Source
E-commerce-related last-mile logistics have a great impact on cities. Recent years have seen sustained growth in e-commerce in most developed countries, a trend that has only been reinforced by the COVID-19 pandemic. The perceived impact of this phenomenon varies depending upon the perspective of the players involved: individual members of the public, companies, or the public administrations. Tackling the issue from these perspectives, the goal of this article is to explore the kinds of impact t...
Source
Aug 1, 2020·Journal of Advanced Transportation2.42
#1Wen Xu (NPU: Northwestern Polytechnical University)H-Index: 1
#2JiaJun Li (NPU: Northwestern Polytechnical University)H-Index: 1
The time-dependent vehicle routing problems have lately received great attention for logistics companies due to their crucial roles in reducing the time and economic costs, as well as fuel consumption and carbon emissions. However, the dynamic routing environment and traffic congestions have made it challenging to make the actual travelling trajectory optimal during the delivery process. To overcome this challenge, this study proposed an unconventional path optimization approach, fissile ripple ...
Source
12
This website uses cookies.
We use cookies to improve your online experience. By continuing to use our website we assume you agree to the placement of these cookies.
To learn more, you can find in our Privacy Policy.