An indirect search algorithm for disaster restoration with precedence and synchronization constraints
Tóm tắt
When a massive disaster occurs, to repair the damaged part of lifeline networks, planning is needed to appropriately allocate tasks to two or more restoration teams and optimize their traveling routes. However, precedence and synchronization constraints make restoration teams interdependent of one another, and impede a successful solution by standard local search. In this paper, we propose an indirect local search method using the product set of team-wise permutations as an auxiliary search space. It is shown that our method successfully avoids the interdependence problem induced by the precedence and synchronization constraints, and that it has the big advantage of non-deteriorating perturbations being available for iterated local search.
Tài liệu tham khảo
Afifi, S, Dang, D-C, Moukrim, A: A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints. In: Learning and Intelligent Optimization, LNCS 7997, pp. 259–265. Springer (2013). http://www.springer.com/la/book/9783642449727.
Bredström, D, Rönnqvist, Mikael: Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. Eur. J. Oper. Res. 191(1), 19–31 (2008). Elsevier.
Derigs, U, Döhmer, T: Indirect search for the vehicle routing problem with pickup and delivery and time windows. OR Spectrum 30(1), 149–165 (2008).
Drexl, M: Synchronization in vehicle routing-a survey of vrps with multiple synchronization constraints. Transp. Sci. 46(3), 297–316 (2012).
Li, H, Lim, A: A metaheuristic for the pickup and delivery problem with time windows. Intl. J. Artif. Intell. Tools 12(02), 173–186 (2003).
Li, Y, Lim, A, Rodrigues, B: Manpower allocation with time windows and job-teaming constraints. Nav. Res. Logist. (NRL) 52(4), 302–311 (2005).
Nonobe, K, Ibaraki, T: Formulation and tabu search algorithm for the resource constrained project scheduling problem. In: Essays and Surveys in Metaheuristics, pp. 557–588. Springer (2002). http://www.springer.com/la/book/9780792375203.
Pankratz, G: A grouping genetic algorithm for the pickup and delivery problem with time windows. Or Spectrum 27(1), 21–41 (2005).
Watanabe, I, Kenichi, T, Satoshi, U: An optimal rout planning method for emergency restoration work in natural disasters. CRIEPI Research Report(R07025) (2008). http://criepi.denken.or.jp/jp/kenkikaku/report/detail/R07025.html.
Watanabe, I, Kenichi, T, Satoshi, U: An optimal allocation method of restoration teams for emergency restoration work. CRIEPI Research Report(R08008) (2009). http://criepi.denken.or.jp/jp/kenkikaku/report/detail/R08008.html.
Yamashita, M, Funakoshi, M, Ishii, H, Kashiwagi, T, Moki, M: Advanced approaches to respond to emergency disasters in kyushu electric’s distribution department. The papers of Technical Meeting on Power Systems Engineering. IEE Japan, 143 (2012). (in Japanese without abstract). https://ieej.ixsq.nii.ac.jp/ej/%3Factive_action=repository_view_main_item_detail%26page_id=13%26block_id=1%25208%26item_id=55303%26item_no=1.