Project topics and materials
Get Complete Project Material File(s) Now! »
Exchange
The third move operator that we adapt for the MCARPTIF is exchange, illustrated in Figure 5.8. An exchange move involving Ti;j;k = u and Tl;m;n = v consists of replacing arc u with v, and v with u. The cost of the move is then the sum of the two replacement costs. The cost of replacing an arc, u, with another arc, v, can be calculated as shown in Figure 5.9, which depends on the position of u relative to IF visits.
The conditions for an exchange move to be feasible are shown in Figure 5.10. The depot and IF arcs cannot be exchanged. When arcs are in the same subtrip, an arc cannot be exchanged with itself, and not with its preceding or following arc. For the latter, the move is identical to relocating an arc in-front of its predecessor. The cost of such a move is not covered by the replacement costs shown in Figure 5.9 and is thus not evaluated with exchange. When arcs u and v are in dierent subtrips, the load changes of both substrips have to be checked for capacity violations. Similarly, if the arcs are in dierent routes, the route cost changes also have to be checked against route duration limits. Algorithm 5.7 nds and returns the best exchange move between subtrips Ti;j and Tl;m. Exchanging arc u with arc v is the same is exchanging arc v with arc u, hence why line 5 is specied for n = k to jTl;mj ? 1. This avoids the same move being evaluated twice. The algorithm also checks if using either one or both of the inverted arcs as a replacement results in a better move. If both u and v can be inverted, there are four exchange combinations that are checked between u and v.
Algorithm 5.8 nds and returns the best exchange move among all subtrip pairs, including exchanging arcs within the same subtrip. Each two arc combination set, fu; vg 2 RT , is considered for exchange. Since inverting the arcs is also considered the computational complexity of nding the best exchange move in an LS iteration is O(R2). The load and route cost changes are unique per move, so we do not apply pre-move feasibility checks to accelerate the search.
Cross
The second last operator that we develop for the MCARPTIF is cross, which is a version of two-opt performed between two dierent routes. The cross move is illustrated in Figure 5.11. First, the two dierent routes are split at specic positions to form four partial routes. The two partial routes representing the end portions of the original routes are then swapped and linked with the two partial routes representing the beginning portions of the original routes. Routes are crossed at arcs Ti;j;k = u and Tl;m;n = v with splits performed between Ti;j;k?1 and u, and between Tl;m;n?1 and v. The cost of the move consists of the cost of splitting the route, and then linking the resulting partial routes.
The most regular cross move involves positions that are preceded by arc tasks, with the conditions for the move, as well as its cost and feasibility checks shown in Figure 5.12.
To check the feasibility of the move it is necessary to determine subtrip loads as well as route costs of all four partial routes, resulting from the two splits. The combined load of subtrips from partial routes are then checked against vehicle capacity limits, and the cost of the combined routes are checked against the route duration limit.
The move costs and feasibility checks for cases where Ti;j;k = u is preceded by an arc task, and Tl;m;n = v is either the last or rst IF, or the rst arc after an IF, are shown in Section 5.B at the end of the chapter. In certain cases, partial routes are linked through IF visits and the load feasibility check need not be performed. In other cases, the move reduces the total number of IF visits over both routes. There are also unique moves between arcs that are not preceded by arc tasks, including a move that results in an entire route being appended to another, thus reducing the eet size. A number of moves results in the same neighbouring solution, and all need not be evaluated. A few moves also result in moves identical to relocate and exchange moves, particularly when a cross move involves the last arc tasks of both routes. Such moves can be skipped if relocate and exchange are used in conjunction with cross.
The best cross move between subtrips Ti;j and Tl;m, where i 6= l can be found using Algorithm 5.9, and the best cross move among all subtrip pairs belonging to dierent routes can be found using Algorithm 5.10. Each unique two arc combination between dierent routes is considered for a cross. The computational complexity of nding the best cross move is thus O(jRT j2).
1 Introduction
1.1 Municipal solid waste collection and transportation
1.2 Capacitated Arc Routing Problems
1.3 Problem statement
1.4 Research design
1.5 Research methodology
1.6 Document structure
2 Capacitated Arc Routing Problems in literature
2.1 Arc routing problems in literature
2.2 Extensions of the Capacitated Arc Routing Problem
2.3 Solution approaches for Capacitated Arc Routing Problems
2.4 Evaluating heuristics
Chapter appendix
3 Splitting procedures
3.1 Introduction
3.2 Splitting procedures for the CARP and CARPTIF
3.3 New splitting procedures
3.4 Computational results
3.5 Conclusion
4 Constructive heuristics
4.1 Introduction
4.2 Constructive heuristics for CARPs
4.3 Constructive heuristics for the MCARPTIF
4.4 Computational results
4.5 Main endings
4.6 Conclusion
Chapter appendix
5 Basic local search heuristics
5.1 Introduction
5.2 Local search for the CARP and MCARP
5.3 Basic local search for the MCARPTIF
5.4 Computational results
Chapter appendix
6 Accelerated local search heuristics
6.1 Introduction
6.2 Acceleration mechanisms for the CARP and VRP
6.3 Accelerated and extended LS for the MCARPTIF
6.4 Computational results
6.5 Conclusion
Chapter appendix
7 An accelerated tabu search metaheuristic
7.1 Introduction
7.2 Tabu search for the MCARPTIF
7.3 Computational results
7.4 Conclusion
Chapter appendix
8 Research contributions and future work
8.1 Research aims
8.2 Research contributions
8.3 Future research opportunities
Bibliography
