Academic Journal
A scatter search algorithm for time-dependent prize-collecting arc routing problems
| العنوان: | A scatter search algorithm for time-dependent prize-collecting arc routing problems |
|---|---|
| المؤلفون: | Riahi, Vahid, Newton, MA Hakim, Sattar, Abdul |
| بيانات النشر: | Elsevier |
| سنة النشر: | 2021 |
| المجموعة: | Griffith University: Griffith Research Online |
| مصطلحات موضوعية: | Applied mathematics, Numerical and computational mathematics, Science & Technology, Technology, Computer Science, Interdisciplinary Applications, Engineering, Industrial, Operations Research & Management Science |
| الوصف: | Time-dependent prize-collecting arc routing problems (TD-PARPs) generalise the regular prize-collecting arc routing problems (PARPs). PARPs have arcs associated with collectable prizes along with travelling costs. TD-PARPs allow travel times to vary at the travelling horizon so that real-life uncertain factors such as traffic and weather conditions can be taken into account. A TD-PARP is to find a travelling route that maximises the profit i.e. total collected prizes minus total travelling costs. TD-PARPs have two facets: selecting a subset of arcs to be travelled and scheduling the selected arcs in the travelling route. TD-PARPs have not been studied much although they are more realistic and generic. In this paper, we first propose a set of deterministic heuristic search algorithms that range from a simple procedure producing quite good results in a fraction of a CPU second to a more extensive procedure producing high-quality results but at the expense of slightly extra CPU time. In this paper, we then propose a meta-heuristic based scatter search (SS) algorithm for TD-PARPs. For the improvement method in the SS algorithm, we propose a multi-operator algorithm that incorporates various neighbourhood operators to diversify the local exploration. For the combination method in the SS algorithm, we propose a 2-level path relinking procedure, which explores combinations of visited and unvisited arcs using two different operators. To control the diversity of the solutions in the SS algorithm, we propose a new effective distance measurement. The experimental results on standard benchmark problems indicate that the proposed SS algorithm significantly outperforms the state-of-the-art existing methods. ; Full Text |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| تدمد: | 0305-0548 |
| Relation: | Computers & Operations Research; Riahi, V; Newton, MAH; Sattar, A, A scatter search algorithm for time-dependent prize-collecting arc routing problems, Computers & Operations Research, 2021, 134, pp. 105392; http://hdl.handle.net/10072/415080 |
| DOI: | 10.1016/j.cor.2021.105392 |
| الاتاحة: | http://hdl.handle.net/10072/415080 https://doi.org/10.1016/j.cor.2021.105392 |
| Rights: | http://creativecommons.org/licenses/by-nc-nd/4.0/ ; © 2021 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). ; open access |
| رقم الانضمام: | edsbas.2DD0FAB0 |
| قاعدة البيانات: | BASE |
| تدمد: | 03050548 |
|---|---|
| DOI: | 10.1016/j.cor.2021.105392 |