Node, edge, arc routing and turn penalties: Multiple problems - one neighborhood extension

摘要

Arc routing problems have many applications such as snow plowing, refuse collection, maintenance and postal service. Practical issues are incorporated in to these problem objective functions using constraints and decision sets resulting in wide variety of problems. In many problems of this type exact solutions may not exist and hence heuristic approaches are used for this purpose. Arc routing is different from node routing as this needs detailed network information and transversal orientations. Node routing is based on shortest routes and is based on the distance matrix. The arc routing have in to account orientations as well as delays at intersections and turn restrictions. Recent arc routing problems are using capacitated arc routing (CARP) heuristics also take in to account service orientations via additional neighborhoods. Since changes of orientation are only in specific moves, the results may not be universal. This has resulted in the development of metaheuristics that are not problem specific and can be used in many similar problems. This paper considers a broad class of arc routing variants, with services on arcs, nodes, and edges as well as possible turn penalties. These problems are formulated as four main decision sets: assignment of services to routes, sequencing, mode choices and paths between services. Mode choices represent different ways of fulfilling a service such as either direction of a street or on a different lane etc. These choices are of the type CARP where different service orientations are possible for each edge, and many other advanced applications. A solution is formulated as a sequence of services and alternate sequence as well as assignment decisions is heuristically enumerated. The optimal choices are derived using dynamic programming. This approach is rarely used because of its computational complexity. This difficulty is overcome by the proposed approach where each move can be evaluated in amortized 0(1). These evaluations require only time required for the elementary operations in a capacitated vehicle routing problem. The difficult decision sets can be fully concealed in the dynamic programming sub-problems. To examine the improvement capabilities, two classical vehicle routing metaheuristics are integrated namely the iterated local search (ILS) of Prins (Ref. 1) and the unified hybrid genetic search of Vidal et al. (Ref. 2) on many arc routing variants and found that the proposed heuristic achieved results of high quality in all the cases. (74 refs.).