19-07-2014, 02:09 PM
Vehicle Routing Problem
Vehicle Routing Problem.ppt (Size: 742.5 KB / Downloads: 10)
Vehicle Routing Problem
Find best vehicle route(s) to serve a set of orders from customers.
Best route may be
minimum cost,
minimum distance, or
minimum travel time.
Orders may be
Delivery from depot to customer.
Pickup at customer and return to depot.
Pickup at one place and deliver to another place
Design to Dynamic Programming Algorithm
The DPA consists of two parts:
route calculation module (RCM), which is used to search the scheme of optimal path.
dynamic programming module (DPM), which is used to deal with real-time traffic information, and call the route calculate module timely to adapt the routes scheme
Route Calculation Module
Chaos phenomenon can experience all the states in a
certain area non-repeatedly, we utilize the Logistic equation to obtain chaos queues.
λn+1 = μλn(1-λn)
Where n=1,2,…MG, n denotes the current generation,
MG is the maximum number of iterations. {λn} denote the chaos queues, 0 ≤ λn ≤1; μ is the controls parameter, let μ = 4 , then the system will be in completely chaos state.
Exchange operator: update chaos queues{λ1n } {λ 2n }, then generate integer J1 in domain [2, N] by (1).
J1 =int(1+Nm λ1n) (1)
Similarly, generate an integer J2 . Where, int( x) denotes to get the integral part of x. If J1 ≠ J2 , Then exchange the elements at position 1J and 2J in the solution vector, keep other elements immovable
Dynamic Programming Module
Step1: Commit the vehicle driving forward following the optimal scheme worked out by RCM.
Step2: Estimate the influence of traffic network, if the critical value exceeds, call RCM to re-plan the routes scheme; else jump to Step3.
Step3: Analyse the current status, if the vehicle has reached the current target node, jump to Step4; else loop to Step1.
Step4: Return routes calculation: set the depot N0 as the target node, and the request node as the start node, taking the final scheme when the vehicle driving to the request node as the original scheme, repeat Step1 to Step3, until the vehicle returns to N0.
Result Analysis
Traffic subnet with 1 depot and 8 nodes, whereas utilize the distance between the nodes to denotes the corresponding distance of the roads (in real world we take the actual distance). The location of the depot and nodes are as following: N0(0,0) , N1(10,5), N2(10, -5) , N3(20,8), N4(20,0), N5(20, -8), N6(26,6) , N7(26, -6),N8(30,0).
Supposing the evaluation value EVij is obtained by certain evaluating and forecast strategy, the link constraints and the evaluation value of each road is shown.
Set the parameters as follows: MG =2000,β = 0.9.
Dynamic Programming Module
Case2: Supposing the vehicle has left the depot, when it is approaching N4, because of land slide, the road I47 damaged, making the capacity of I4,7 worse suddenly,EV47 = 0.05, the influence to other roads is little. Here, re- planning of the roads is needed.
Conclusion
Recent technological advances in communication and information such as ITS and GPS make dynamic programming for the VRPs realizable.
We studied the VRPs based on real-time traffic information, the mathematic model is formulated and a dynamic programming algorithm is proposed.
From the analysis of the performance dealing with the cases of initial-state, road-damaged and road- congested, we conclude that the proposed DPA is a feasible and efficient algorithm to