E-resources
-
Riahi, Vahid; Hakim Newton, M.A.; Sattar, Abdul
Computers & operations research, 10/2021, Volume: 134Journal Article
•Studying the prize-collecting arc routing problems (PARPs) with real-time scenarios.•Proposing constructive heuristics and metaheuristic algorithm to solve the problem.•Outperforming the best-existing methods in the literature. 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.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.