Akinola Ogunsemi
Job assignment problem and traveling salesman problem: a linked optimisation problem.
Ogunsemi, Akinola; McCall, John; Kern, Mathias; Lacroix, Benjamin; Corsar, David; Owusu, Gilbert
Authors
Professor John McCall j.mccall@rgu.ac.uk
Professorial Lead
Mathias Kern
Benjamin Lacroix
Dr David Corsar d.corsar1@rgu.ac.uk
Senior Lecturer
Gilbert Owusu
Contributors
Max Bramer
Editor
Frederic Stahl
Editor
Abstract
Linked decision-making in service management systems has attracted strong adoption of optimisation algorithms. However, most of these algorithms do not incorporate the complexity associated with interacting decision-making systems. This paper, therefore, investigates the linkages between two classical problems: job assignment problem and travelling salesman problem (JAPTSP) of a service chain system where service personnel perform tasks at different locations. We formulate a novel mathematical model from a linked optimisation perspective with objectives to minimise job cost and total travel distance simultaneously. We present three algorithmic approaches to tackling the JAPTSP: Nondominated Sorting Genetic Algorithm for Linked Problem (NSGALP), Multi-Criteria Ranking Genetic Algorithm for Linked Problem (MCRGALP), and Sequential approach. We evaluate the performance of the three algorithmic approaches on a combination of JAP and TSP benchmark instances. Results show that selecting an appropriate algorithmic approach is highly driven by specific considerations, including multi-objective base performance metrics, computation time, problem correlation and qualitative analysis from a service chain perspective.
Citation
OGUNSEMI, A., MCCALL, J., KERN, M., LACROIX, B., CORSAR, D. and OWUSU, G. 2022. Job assignment problem and traveling salesman problem: a linked optimisation problem. In Bramer, M. and Stahl, F (eds.) Artificial intelligence XXXIX: proceedings of the 42nd SGAI (Specialist Group on Artificial Intelligence) Artificial intelligence international conference 2022 (AI 2022), 13-15 December 2022, Cambridge, UK. Lecture notes in computer science (LNCS), 13652. Cham: Springer [online], pages 19-33. Available from: https://doi.org/10.1007/978-3-031-21441-7_2
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | 42nd SGAI (Specialist Group on Artificial Intelligence) Artificial intelligence international conference 2022 (AI 2022) |
Start Date | Dec 13, 2022 |
End Date | Aug 30, 2022 |
Acceptance Date | Dec 5, 2022 |
Online Publication Date | Dec 5, 2022 |
Publication Date | Dec 31, 2022 |
Deposit Date | Jan 10, 2023 |
Publicly Available Date | Dec 6, 2023 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Pages | 19-33 |
Series Title | Lecture Notes in Computer Science (LNCS) |
Series Number | 13652 |
Series ISSN | 0302-9743; 1611-3349 |
Book Title | Artificial intelligence XXXIX: proceedings of the 42nd SGAI (Specialist Group on Artificial Intelligence) Artificial intelligence international conference 2022 (AI 2022) |
ISBN | 9783031214400 |
DOI | https://doi.org/10.1007/978-3-031-21441-7_2 |
Keywords | Linked optimisation problem; Multi-criteria decision making; Multi-objective optimisation; Service chain optimisation |
Public URL | https://rgu-repository.worktribe.com/output/1853737 |
Files
OGUNSEMI 2022 Job assignment problem (AAM)
(935 Kb)
PDF
You might also like
Facility location problem and permutation flow shop scheduling problem: a linked optimisation problem.
(2022)
Presentation / Conference Contribution
On the multi-objective optimization of wind farm cable layouts with regard to cost and robustness.
(2024)
Presentation / Conference Contribution
Cost and performance comparison of holistic solution approaches for complex supply chains on a novel linked problem benchmark.
(2024)
Presentation / Conference Contribution
Ensemble-based relationship discovery in relational databases.
(2020)
Presentation / Conference Contribution