A Metaheuristic for the Periodic Location-Routing Problem
The well-known Vehicle Routing Problem (VRP) has been generalized toward tactical or strategic decision levels of companies but not both. The tactical extension or Periodic VRP (PVRP) plans trips over a multi-period horizon, subject to frequency constrain
- PDF / 168,031 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 200 Views
ntroduction Researches have shown that separation of location and routing decisions often leads to suboptimal solutions [11]. The Location-Routing Problem (LRP) overcomes this drawback. However, only very recent papers consider both capacitated routes and depots [13, 2, 8, 7, 9]. Beside the strategic aspect of depot location, a focus on tactical decision such as Vehicle Routing Problems (VRP) leads to consider some extensions. One of these consists in integrating frequency constraints on visited customers under a given multiperiod horizon. The resulting problem is known as periodic VRP or PVRP. The methods used to solve PVRP are mainly heuristics [4, 12, 3, 6].
160
Caroline Prodhon
In this paper, the LRP and the PVRP are combined for the first time into an even more realistic problem: the periodic LRP or PLRP. It is defined on an horizon H and a complete, weighted and undirected network G = (V, E, C). V is a set of nodes comprised of a subset I of m possible depot locations and a subset J = V \I of n customers. cij is the traveling cost between any two nodes i and j. A capacity Wi and an opening cost Oi are associated with each depot site i ∈ I. Each customer j ∈ J has to be served with a given frequency over H, and Combj is its set of possible combinaisons of serviced days. djlr is the demand of customer j on the day l of combinaison r ∈ Combj . A set K of identical vehicles of capacity Q is available each day. A vehicle used at least once from a depot during H incurs a fixed cost F and it can perform one single route per day. The following constraints must hold: i) each customer j must be served exclusively on each day l of exactly one of the combinaison r ∈ Combj by one vehicle and at the amount djlr ; ii) the number of routes performed by day must not exceed N ; iii) each route must begin and end at the same depot within the same day and its total load must not exceed Q; iv) the total load of the routes assigned to a depot on any day l ∈ H must fit the capacity of that depot. The objective is to find which subset of depots to open, which combinaison of visit days to assign to each customers and which routes to perform, in order to minimize the total cost. The PLRP is NP -hard since it reduces to the VRP when m = 1 and |H| = 1. The proposed method to solve it is a metaheuristic that tries to keep a global vision on the problem by taking into consideration several decision levels when making a choice during the construction of a solution. Section 2 describes the framework of the proposed algorithm. The performances of the method are evaluated in Section 3. Some concluding remarks close the paper.
2 Iterative Metaheuristic 2.1 Depot Location The location phase of the algorithm begins by considering a fictive day during which the whole set of customers has to be served. The proposed aggregation of the data comes from the fact that the same depots has to be opened all over H. Thus, we should choose the depots in accordance to the entire set J. A fictive capacity, equal to Wi ×|H|, is given to each depot i ∈ I. The deman
Data Loading...
