Job assignment problem and traveling salesman problem: a linked optimisation problem.

Ogunsemi, Akinola; McCall, John; Kern, Mathias; Lacroix, Benjamin; Corsar, David; Owusu, Gilbert

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

• Conference Name: 42nd SGAI (Specialist Group on Artificial Intelligence) Artificial intelligence international conference 2022 (AI 2022)
• Conference Location: Cambridge, UK
• 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
• 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