24 Hours Operations Research

• Problem definition
• Solution approach
• Additional information
• PDF

Rollon-Rolloff problems
E1CRP is a special case of the Distance-constrained uncapacitated Vehicle Routing Problem (D-VRP) see [8, 9]. D-VRP arises whenever in a VRP problem arcs have non negative weights and the only feasibility side constraint is to not exceed a maximum weight for each route, that is, there is a single side constraint function and it is defined on the arcs rather than on the nodes.

E1CRP can be formulated as a D-VRP, where the arc weight is the total time needed to carry out all the activities modeled by the arc, including service time at the head node; the route weight is its duration, and the maximum weight allowed in each route corresponds to the maximum duration of the drivers’ shift.

However, despite of the hardness of D-VRP, heuristic approaches seem to provide good quality results when the D-VRP is defined on special graphs, modelling container routing in waste collection applications, so called Rollon-Rolloff vehicle routing problems [1, 4, 5, 11, 15]. All these problems share several features with E1CRP as: a homogeneous fleet of vehicles, carrying one container at a time, operates a set of routes from and to the depot to serve all requests within a given time limit; requests concern full containers to be emptied or relocated, and/or deliveries of empty containers; several types of containers are given which can be carried by any vehicle. However [1, 4, 5, 11] have an unlimited number of empty spare containers.

Neighbourhood based metaheuristics
Neighbourhood based metaheuristics provide a viable tool for tackling routing problems. Beside Tabu Search, other relevant frameworks of this class are Simulated annealing [7], Variable Neighbourhood Search [6], GRASP [14], Iterated Local Search [10] and Very Large Neighbourhood Search [3].

In the Tabu Search developed for the E1CRP, for enlarging the search space we allow unfeasible moves during the search, i.e., moves generating a route exceeding the maximum allowed duration. Therefore, we introduce a variable objective function which takes into account the two objectives and the unfeasibility. The effectiveness of this approach has been assessed in [2].

Moreover in order to better explore the solution space, we introduce two strategies to intensify and diversify. The intensification strategy consists in confining the search for a given number of iterations into a subregion characterized by a fixed number of routes, one less than the number of routes in the solution just before the intensification.

The diversification strategy occurs after a given number of consecutive iterations monotonically non decreasing, as follows: all routes composed by one tour are recomputed by splitting the single tour in two separate tours, and the broken arcs are made tabu in order to avoid successively merging. The basic idea is to give more degree of freedom both to neighborhood search and to the algorithm for the bin packing problem.

Neighbourhoods for VRP
Beside the string exchange and relocation move described in the solution approach section (also called cross exchange in [16]), many other moves are specific for VRP.

• 2-opt* (introduced by [13]) is a special case of the cross exchange move, obtained when the last node is the depot in both the two sequences of arcs considered for the swapping (so just two arcs are exchanged rather than four):

  

• Or-opt (introduced in Or’s Ph.D. thesis in ´76) moves a sequence of three consecutive nodes or less from one tour to another. It can be seen like a special case of the cross exchange move when an empty sequence of nodes is removed from one of the two tours:

  

• λ-interchange (introduced by [12]) is a generalization of the cross exchange: it selects two subsets of nodes, with cardinality less than or equal to λ, from two different tours and exchange them. However, the size of this neighbourhood quickly becomes very large, even for small values of λ. A useful and manageable neighbourhood can be obtained by restricting the exchanges to consecutive nodes in both routes (thus, leading to cross exchanges).

• intra-tour moves involve a single tour rather than pairs of tours: every move for the Travelling Salesman Problem (TSP) can be used for this aim. For instance the 3-opt move consists in the deletion of three non consecutive arcs and in the reconnection of the four generated subsequences without arc reversing:

  

References:
More information about hub location problems, can be found in the following links.

• [1] C. Archetti and M.G. Speranza. Vehicle routing in the 1-skip collection problem. Journal of the Operational Research Society, 55(7):717–727, 2004.

• [2] R. Aringhieri and M. Dell’Amico. Comparing Metaheuristic Algorithms for the SONET Network Design Problems. Journal of Heuristics, 11(1):35–57, 2005.

• [3] R.K. Ahujaa, O. Ergun, J. B. Orlin, A. P. Punnend. A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics 123: 75 – 102, 2002.

• [4] R. Baldacci, L. Bodin, and A. Mingozzi. The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem. Computer & Operations Research, 33:2667-2702,2006.

• [5] L. Bodin, A. Mingozzi, R. Baldacci, and M. Ball. The rollon–rolloff vehicle routing problem. Transportation Science, 34(3):271–288, 2000.

• [6] P. Hansen and N. Mladenovic. Variable neighbourhood search: Principles and applications. European Journal of Operations Research, 130:449–467, 2001.

• [7] S. Kirkpatrick, C.D. Gelatt; M.P. Vecchi. Optimization by Simulated Annealing. Science, New Series, Vol. 220, No. 4598, pp. 671-680, 1983.

• [8] G. Laporte, Desrochers M., and Y Norbert. Two exact algorithms for the distance-constrained vehicle routing problem. Networks, 14:161–172, 1984.

• [9] C. Li, D. Simchi-Levi, and M. Desrochers. On the distance constrained vehicle routing problem. Operations Research, 40(4):790–799, 1992.

• [10] H.R. Lourenço, O.C. Martin,, T. Stützle. Iterated Local Search.

• [11] L. De Muelemeester, G. Laporte, F. V. Louveaux, and F. Semet. Optimal sequencing of skip collections and deliveries. Journal of Operational Research Society, 48:57–64, 1997.

• [12] I.H. Osman. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41: 421-451, 1993.

• [13] J.Y. Potvin and J.M. Rousseau. An exchange heuristic for the vehicle routing problem with time windows, Journal of the Operational Research Society 46: 1433-1446.

• [14] M.G.C. Resende. Greedy Randomized Adaptive Search Procedures (GRASP). Encyclopedia of Optimization, C. Floudas and P.M. Pardalos, eds., Kluwer Academic Press, vol. 2, pp. 373-382, 2001.

• [15] A. Sbishi and R. W. Eglese. Combinatorial optimization and green logistics. 4OR, 5(2):99–116, 2007.

• [16] E.Taillard, P.Badeau, M.Gendreau, F.Guertin, J. Potvin. A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation science 31: 170-186, 1997.

• [17] A. Van Breedam. Comparing descent heuristics and metaheuristics for the vehicle routing problem. Computer & Operations Research, 28: 289-315, 2001.

For detailed information about this project contact: Maurizio Bruglieri.