Analytics and machine learning in scheduling and routing research

1. Background

This special issue largely originated from various discussions during several cross-domain, multi-disciplinary conferences and workshops, especially the 9th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA2019), which attracted scientists, researchers and practitioners from Computer Science, Operations Research as well as Business and Management. It became increasingly clear that the next stage of digitisation and enterprises digital transformations must call for advanced modelling and computing methodologies that can handle the scale, non-linearity, and uncertainties widely present in complex systems. This special issue was made available to promote the multi-disciplinary studies and focuses on research efforts in hybridising analytical optimisation with machine learning methods when solving difficult scheduling and vehicle routing problems.

In the past several years, there has been a growing research effort that attempts to bridge the gap between analytical models and learning-based optimisations. This special issue aims to promote the use of this type of modelling and solution methods in production scheduling and vehicle routing. Specifically, we attract high-quality scheduling and routing research papers that develop or apply integrated analytics and optimisation methods that are not only flexible and robust under uncertainty but can also generate models and solutions that are insightful and (relatively) easy to interpret.

2. Summary of papers

The special issue was advertised in the related research communities and a total of 54 papers were submitted and peer-reviewed. Finally, 18 of them were accepted for publication in International Journal of Production Research. We hope the papers are useful to the readers. We now introduce them hereafter.

The special issue starts with a review paper from Bai et al. (2022). It provides an extensive review of vehicle routing (VRP) researches that use both analytical optimisation approaches and machine learning (ML) modules and mechanisms. In total, more than 200 papers were reviewed and classified into 4 categories which are: machine learning assisted VRP modelling, machine learning guided VRP decomposition strategies, machine learning guided perturbative VRP algorithms, and finally learning to construct VRP solutions. The review also summarises the underlining factors that lead to diversity and dynamics of the VRP problems, followed by comparative discussions of the perturbative optimisation vs. generative optimisation methods as well as model-driven vs. data-driven methods.

Following this review paper, the special issue then includes the four VRP-related papers. Huang et al. (2022) address a shortest path interdiction problem via a reinforcement learning method using the popular pointer network architecture for variable problem-size encoding. Demantova et al. (2022) study an inventory-routing problem (IRP) that jointly optimises the inventory and associated routing. A time window is also imposed to each customer. A combination of different techniques is proposed including cutting, local branching and local search. Promising results were reported in comparison with existing methods. Hu et al. (2022) investigate an AGV (autonomous guided vehicles) routing problem encountered in a container port terminal. The main challenge addressed in this paper is to prevent conflicting routes between AGVs in complex environments. A multi-agent deep deterministic policy gradient method is proposed for the problem. Bashiri et al. (2022)'s work describes a two-stage stochastic vehicle routing problem for the purpose of asset protection in an event of wildfire. Machine learning modules are used to extract possible scenarios based on the historical data of the random variables. An adaptive large neighbourhood search method (ALNS) is then developed to tackle this problem.

Heni et al. (2022) investigate various machine learning approaches to improve the prediction of the fuel consumption in transportation and logistics. The problem is challenging because of the variations in vehicle speed, road traffic, weather, etc. The resulting neural network models after training can be used in solving the associated vehicle routing problem. Bing Chen et al. (2020) propose a multi-objective bus scheduling optimisation method whose input parameters are estimated through various machine learning-based predictive models. The experimental analysis shows superior capabilities by the proposed approach in adapting to uncertainties related to passenger demands and travel times.

The second part of the issue is dedicated to production scheduling. Heger and Voss (2022) study a hyper-heuristic method that adaptively selects among a set of priority-based sequencing rules. A reinforcement learning-based module is embedded to train the algorithm through a simulation for flexible flow shop problem. The proposed method is deemed to have better comprehension levels and can reduce the mean tardiness by up to 5%. Kim et al. (2022) describe a re-entrant flow shop problem and propose a learning-based approach using gradient-based evolutionary strategy (GES). This can be considered as a typical data-driven method. The performance is evaluated by comparing it with two other popular evolutionary algorithms, namely a genetic programming and a genetic algorithm. Shufan et al. (2022) present some theoretical work on a same problem but with special conditions (i.e. unit processing time) and report some errors in two previously published heuristics. Machine learning-based analysis is used to differentiate the features between the studied heuristics.

Li et al. (2020) describe a closed-loop approximate dynamic programming algorithm for a resource levelling problem under multiple uncertainties. Through simulation-based experiments, the authors demonstrate superior performance by their algorithm when compared with the state-of-the-art methods for the same problem. Efatmaneshnik and Shoval (2022) investigate a stochastic job shop scheduling problem which is modelled as a Markovian process and heuristics are used to tackle the problem. The paper also discusses how the proposed model could support the machine learning tools. Fan, Wang, and Liu (2020)'s study is about a two-agent batch scheduling problem on parallel machines. Online algorithms are studied and their worst-case performances are analysed. Ying et al. (2020) investigate a flexible permutation flow-shop scheduling problem faced in assembly factories with multiple suppliers. Tang et al. (2022) study a collaborative production scheduling problem with the practical consideration of order-merging. Like Ying et al. (2020)'s work, the main contribution is related to the extensions of the existing mathematical models by taking into consideration of more practical factors.

The last part of our special issue includes three papers that focus on general combinatorial optimisation problems faced in real-life. In Shajalal, Hájek, and Abedin (2022)'s work, a supply chain management problem with back-orders is considered and uncertainties (for example, the amount of back-orders) are handled by predictive models based on a deep neural network. In Lu et al. (2022)'s work, a personnel scheduling problem is described and uncertain factors are analysed and modelled. A meta-heuristic method was proposed to address the complexities of the problem. Lastly, Ming Chen et al. (2022) illustrate how data-driven approaches can be used to discover the main issues in university timetabling which lead to poor students performance and delayed graduation. Optimisation approaches are then proposed to address each of the main issues to improve the course timetabling preference satisfaction in terms of seat capacity and time windows.

Since the closure of this special issue, there have been increasingly more and more research works and papers on integrating analytical approaches and machine learning in addressing real-life scheduling and vehicle routing problems. We are very pleased to see this new trend of research and hope this special issue can inspire more exciting and novel research in the related fields.

Additional information

Notes on contributors

Ruibin Bai

Ruibin Bai is Professor at the University of Nottingham Ningbo China and leads the Artificial Intelligence and Optimisation (AIOP) research group. His research areas include computational intelligence, reinforcement learning, combinatorial optimisation, transportation optimisation and digital twins. He is a Senior Member of IEEE and currently serves as a Board Member for EJOR and an Associate Editor for Networks.

Zhi-Long Chen

Zhi-Long Chen received his Ph.D. degree in Operations Research from Princeton University in 1997. He is currently Orkand Corporation Professor of Management Science at the Robert H. Smith School of Business. His research interests cover supply chain scheduling, production and transportation operations, dynamic pricing, and optimisation. Dr Chen has conducted several NSF-funded research projects on integrated production and distribution operations, coordination of dynamic pricing and scheduling, and transportation capacity planning. He is currently serving as an associate editor of Operations Research, POM, IIE Transactions, NRL, Networks, and Journal of Scheduling.

Graham Kendall

Graham Kendall is an Emeritus Professor in the University of Nottingham, Professor Kendall is a Fellow of the British Computer Society (FBCS) and a Fellow of the Operational Research Society (FORS). His research interests include Operations Research, Scheduling, Logistics, Vehicle Routing, Meta- and Hyper-heuristics, Evolutionary Computation and Games.