1,721,149 research outputs found
Time dependent travel speed vehicle routing and scheduling on a real road network: the case of Torino
No full textVehicle 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 dependent travel times work with simplified step functions, discretizing the time horizon in small time intervals. Even if this approach is broadly used, assuming travel times varying with discrete jumps is a strong approximation of real world conditions which evolve continuously. Another strong approximation adopted in the literature is that travel time (or speed) is computed on direct links, while in the real world vehicles travels on a road network, in which Euclidean distances do not hold anymore. In this paper, a vehicle routing problem (VRP) on a real road network with time dependent travel speed expressed by a polynomial function is addressed. Despite the difficulty to work with these kind of function, in this way congestion evolution behavior may be more precisely represented. In real situations, it is common to face different congestion peaks during the day, each one of which generally has different characteristics. Morning peaks are very sharp, i.e. congestion level rapidly increase reaching its maximum value which last for a short time after what congestion rapidly decrease, while evening peaks are generally much more spread across a longer time period and congestion variations are much more smoothed. Step functions, commonly used in practice, cannot represent at all realistic situations and peaks; linear functions may acceptable represents sharp peaks but not wider once. Polynomials, indeed, are able to better describe each type of peak. An application on Torino road network is presented. Speed evolution laws on main arcs are computed basing on real data obtained from an analysis carried out on averaged travel speed measured by an electronic system with 5 minutes intervals over two weeks. Small streets for which this data are not available are supposed to have a constant travel speed. Computational results show that taking advantage on the available information on different rush hour peaks intensity and spread on different arcs, it is possible to obtain better vehicle routing and scheduling plan
A real-life Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet: Formulation and Adaptive Large Neighborhood Search based Matheuristic
No full textIn this paper, a new rich Vehicle Routing Problem that could arise in a real life context is introduced and formalized: the Multi Depot Multi Period Vehicle Routing Problem with a Heterogeneous Fleet. The goal of the problem is to minimize the total delivery cost. A heterogeneous fleet composed of vehicles with different capacity, characteristics (i.e. refrigerated vehicles) and hourly costs is considered. A limit on the maximum route duration is imposed. Unlike what happens in classical multi-depot VRP, not every customer may/will be served by all the vehicles or from all the depots. The planning horizon, as in most real life applications, consists of multiple periods, and the period in which each route is performed is a variable of the problem. The set of periods, within the time horizon, in which the delivery may be carried out is known for each customer. A Mixed Integer Programming (MIP) formulation for MDMPVRPHF is presented in this paper, and an Adaptive Large Neighborhood Search (ALNS) based Matheuristic approach is proposed, in which different destroy operators are defined. Computational results, pertaining to realistic instances, which show the effectiveness of the proposed method, are provided. (C) 2015 Elsevier Ltd. All rights reserved
Assignment of swimmers to events in a multi-team meeting for team global performance optimization
No full textMulti-echelon distribution systems in city logistics
Full text linkIn the last decades
,
the increasing quality of services requested by the cust
omer, yields to the necessity of
optimizing
the whole distribution process.
This goal may be achieved through a smart exploitation of
existing resources other than a clever planning of the whole distribution process. For doing that, it is
necessary to enha
nce goods consolidation.
One of the most efficient way to implement
it
is to adopt
Multi
-
Echelon distribution systems
which are very common in
City Logistic context,
in which they allow
to keep large trucks from the city center, with strong
environmental
a
dvantages
.
The aim of the
paper
is to
review
routing
problems
arising
in City Logistics
, in which multi
-
e
chelon distribution systems are
involved: the
Two Echelon
Location Routing Problem (
2E
-
LRP)
, the Two
Echelon Vehicle Routing
Problem (2E
-
VRP) and Truck and Trailer Routing Problem (TTRP), and to discuss literature on
optimization methods, both exact and heuristic, developed to address these problems
The Hybrid Vehicle Routing Problem
No full textIn this paper the Hybrid Vehicle Routing Problem (HVRP) is introduced and formalized. This problem is an extension of the classical VRP in which vehicles can work both electrically and with traditional fuel. The vehicle may change propulsion mode at any point of time. The unitary travel cost is much lower for distances covered in the electric mode. An electric battery has a limited capacity and may be recharged at a recharging station (RS). A limited number of RS are available. Once a battery has been completely discharged, the vehicle automatically shifts to traditional fuel propulsion mode. Furthermore, a maximum route duration is imposed according to contracts regulations established with the driver. In this paper, a Mixed Integer Linear Programming formulation is presented and a Large Neighborhood Search based Matheuristic is proposed. The algorithm starts from a feasible solution and consists into destroying, at each iteration, a small number of routes, letting unvaried the other ones, and reconstructing a new feasible solution running the model on only the subset of customers involved in the destroyed routes. This procedure allows to completely explore a large neighborhood within very short computational time. Computational tests that show the performance of the matheuristic are presented. The method has also been tested on a simplified version of the HVRP already presented in the literature, the Green Vehicle Routing Problem (GVRP), and competitive results have been obtained
A new large neighborhood search based matheuristic framework for rich vehicle routing problems
No full textIn this paper a New Large Neighborhood Search Based Matheuristic Framework for Rich Vehicle Routing Problems is presented. The innovative aspect of the proposed approach concern the possibility to address large neighborhoods in reasonably small computational time exploiting the search directly by the mathematical model. In this way it is possible to obtain the local minimum respect to the addressed neighborhood, which make the intensification phase of the algorithm more powerful and precise. The method is extremely flexible and can be adapted to many rich vehicle routing problems. This procedure can be used as a stand alone heuristic or can be embedded in a more complex metaheuristic framework such as Variable Neighborhood Search (VNS) and Adaptive Large Neighborhood Search (ALNS). The proposed algorithm has been tested on a new rich Vehicle Routing Problem arising in real life context, the Multi Depot Multi Period Vehicle Routing Problem with Heterogeneous Fleet. Computational results on realistic instances, showing the effectiveness of the proposed method, are provided
A combined multistart random constructive heuristic and set partitioning based formulation for the vehicle routing problem with time dependent travel times
No full textAlthough 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, service times at nodes, and limit on the maximum route duration, is addressed. The objective function consists into minimizing the total travel time. A Multistart Random Constructive Heuristic, (MRCH), in which congestion level is considered, is proposed. The routes obtained by the MRCH are then used as columns in a Set Partitioning formulation. Computational results, carried out on instances derived by VRP instances taken from the literature, show the efficiency and effectiveness of the proposed approach
Optimizing real-life freight-distribution problems
No full textReal-life freight-distribution problems present high degrees of complexity mostly derived from needing to respect a variety of constraints and addressing complex objective functions in which different factors are taken into account. The aim of this article is to point out relevant issues arising in real-life freight-distribution problems and to describe still-open issues and gaps between models and real-life applications. Furthermore, a real-life vehicle-routing problem is presented and a real instance related to regional freight distribution in Piedmont (northwest Italy) is solved by a fast heuristic method. The extreme portability of this method is then discussed
- …
