Routing Vehicles, Algorithms
- PDF / 528,497 Bytes
- 9 Pages / 547.087 x 737.008 pts Page_size
- 40 Downloads / 197 Views
979
Roadway Network Model Emergency Evacuations, Transportation Networks
Root-Mean-Square Error
Depot
Photogrammetric Products
Rough Approximation Approximation
customer
Rough Set Theory Approximation
Route Activity Crime Mapping and Analysis
Routing Data Collection, Reliable Real-Time
Routing Vehicles, Algorithms C HRISTOS D. TARANTILIS Department of Management Science & Technology, Athens University of Economics & Business, Athens, Greece Synonyms Distribution logistics; Fleet management; Vehicle routing problem; Simulated annealing; Threshold accepting method; Record-to-record travel method Definition The Vehicle Routing Problem (VRP) [1] embraces a class of complex combinatorial optimization problems that target the derivation of minimum total cost routes for a number of resources (vehicles) located at a central point (depot) in order to service efficiently a number of demand points (customers). The standard version of VRP (known as basic VRP) is defined on a graph G = (V,A), where
Routing Vehicles, Algorithms, Figure 1 A typical VRP solution
V = {u0 , u1 , . . . ,un } is the vertex set and A = {(ui , uj ): ui , uj ∈ V,i = j} is the arc set of G. Vertex u0 represents a depot (warehouse or distribution centre) that hosts a homogeneous fleet of m vehicles with capacity Q. The remaining vertices correspond to demand points (or equivalently, customers). Each customer ui has a non-negative demand qi . The vector of all customer demands is denoted by q(V). Furthermore, a non-negative cost matrix C = (cij ) is defined on A; usually, the cost cij models the travel time between customers ui and uj . If cij = cji , the problem is symmetric, and it is common to replace A with the edge set E = {(ui , uj ): ui , uj ∈ V,i < j}. The solution to the basic VRP is a set of routes that satisfy the following constraints: a) each route starts and ends at the central depot; b) each customer is visited exactly once; c) every customer’s demand is satisfied; d) the total travel time of the set of routes is minimized. The aim of this chapter is to focus on the annealing-based solution approaches for solving two of the most studied VRP types: the Capacitated VRP (CVRP) and the Distance Constrained VRP (DCVRP) [2]. The additional constraints imposed to model the routing scenarios of the aforementioned VRP types are: • the total demand of the customers covered by a route cannot exceed the capacity of a vehicle Q (for both CVRP and DCVRP); • the total travel time of any vehicle route cannot exceed a pre set upper bound (only for DCVRP). The objective (for both CVRP and DCVRP) is to minimize the sum of travel time. It is important to note that the number of vehicles is either pre-determined or is treated as a decision variable.
R
980
Routing Vehicles, Algorithms
Historical Background In the late 70s, several algorithms were developed for solving VRPs for very small numbers of variables and constraints. Later, since exact algorithms were not capable of consistently solving instances with more than 50 customers,
Data Loading...
