The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem
This article introduces methods for initializing a single-trajectory-based metaheuristic, specifically a simulated annealing (SA) algorithm, using constructive heuristics. These methods are designed to target promising regions within the search space of an nondeterministic polynomial time (NP)-hard...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
PeerJ Inc.
2025-06-01
|
| Series: | PeerJ Computer Science |
| Subjects: | |
| Online Access: | https://peerj.com/articles/cs-2840.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849472916306001920 |
|---|---|
| author | Abdul Kader Kassoumeh Zühal Kartal Ahmet Arslan |
| author_facet | Abdul Kader Kassoumeh Zühal Kartal Ahmet Arslan |
| author_sort | Abdul Kader Kassoumeh |
| collection | DOAJ |
| description | This article introduces methods for initializing a single-trajectory-based metaheuristic, specifically a simulated annealing (SA) algorithm, using constructive heuristics. These methods are designed to target promising regions within the search space of an nondeterministic polynomial time (NP)-hard problem, namely the single allocation p-hub center and routing problem. The objective of this problem is to allocate demand centers to hubs and design vehicle routes such that the maximum distance between all origin-destination pairs is minimized. To analyze the impact of different initial solutions, various constructive heuristics, including greedy and hybrid strategies, have been proposed. Additionally, a problem decomposition approach leveraging domain-specific knowledge has been incorporated through a matheuristic initial solution strategy to enhance the efficiency of the simulated annealing algorithm. This approach generates high-quality initial solutions by first solving the p-hub center problem and then using the obtained hubs and their assignments as inputs to the min-max multiple traveling salesman problem. In this problem, the objective function is formulated differently from the literature by minimizing the longest distance between the two nodes. Several experiments have been conducted on the Turkish network, and upon examining the results, it has been observed that each initial solution generation strategy provides improvements in problem instances with specific characteristics, such as the number of vehicles and nodes. We also observed lower objective function values for all medium- and large-sized test problems taken from the literature, highlighting the effectiveness of the proposed strategies. |
| format | Article |
| id | doaj-art-99a9bbff21ff418caee863cdd8a0e2aa |
| institution | Kabale University |
| issn | 2376-5992 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | PeerJ Inc. |
| record_format | Article |
| series | PeerJ Computer Science |
| spelling | doaj-art-99a9bbff21ff418caee863cdd8a0e2aa2025-08-20T03:24:22ZengPeerJ Inc.PeerJ Computer Science2376-59922025-06-0111e284010.7717/peerj-cs.2840The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problemAbdul Kader Kassoumeh0Zühal Kartal1Ahmet Arslan2Department of Computer Science, Eskisehir Technical University, Eskisehir, TurkiyeDepartment of Industrial Engineering, Eskisehir Technical University, Eskisehir, TurkiyeDepartment of Computer Science, Eskisehir Technical University, Eskisehir, TurkiyeThis article introduces methods for initializing a single-trajectory-based metaheuristic, specifically a simulated annealing (SA) algorithm, using constructive heuristics. These methods are designed to target promising regions within the search space of an nondeterministic polynomial time (NP)-hard problem, namely the single allocation p-hub center and routing problem. The objective of this problem is to allocate demand centers to hubs and design vehicle routes such that the maximum distance between all origin-destination pairs is minimized. To analyze the impact of different initial solutions, various constructive heuristics, including greedy and hybrid strategies, have been proposed. Additionally, a problem decomposition approach leveraging domain-specific knowledge has been incorporated through a matheuristic initial solution strategy to enhance the efficiency of the simulated annealing algorithm. This approach generates high-quality initial solutions by first solving the p-hub center problem and then using the obtained hubs and their assignments as inputs to the min-max multiple traveling salesman problem. In this problem, the objective function is formulated differently from the literature by minimizing the longest distance between the two nodes. Several experiments have been conducted on the Turkish network, and upon examining the results, it has been observed that each initial solution generation strategy provides improvements in problem instances with specific characteristics, such as the number of vehicles and nodes. We also observed lower objective function values for all medium- and large-sized test problems taken from the literature, highlighting the effectiveness of the proposed strategies.https://peerj.com/articles/cs-2840.pdfP-hub center problemP-hub center and routing problemMatheuristicsSimulated annealing |
| spellingShingle | Abdul Kader Kassoumeh Zühal Kartal Ahmet Arslan The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem PeerJ Computer Science P-hub center problem P-hub center and routing problem Matheuristics Simulated annealing |
| title | The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem |
| title_full | The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem |
| title_fullStr | The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem |
| title_full_unstemmed | The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem |
| title_short | The effect of different initial solutions on the metaheuristic algorithms for the single allocation p-hub center and routing problem |
| title_sort | effect of different initial solutions on the metaheuristic algorithms for the single allocation p hub center and routing problem |
| topic | P-hub center problem P-hub center and routing problem Matheuristics Simulated annealing |
| url | https://peerj.com/articles/cs-2840.pdf |
| work_keys_str_mv | AT abdulkaderkassoumeh theeffectofdifferentinitialsolutionsonthemetaheuristicalgorithmsforthesingleallocationphubcenterandroutingproblem AT zuhalkartal theeffectofdifferentinitialsolutionsonthemetaheuristicalgorithmsforthesingleallocationphubcenterandroutingproblem AT ahmetarslan theeffectofdifferentinitialsolutionsonthemetaheuristicalgorithmsforthesingleallocationphubcenterandroutingproblem AT abdulkaderkassoumeh effectofdifferentinitialsolutionsonthemetaheuristicalgorithmsforthesingleallocationphubcenterandroutingproblem AT zuhalkartal effectofdifferentinitialsolutionsonthemetaheuristicalgorithmsforthesingleallocationphubcenterandroutingproblem AT ahmetarslan effectofdifferentinitialsolutionsonthemetaheuristicalgorithmsforthesingleallocationphubcenterandroutingproblem |