The hybrid seru manufacturing mode widely exists in many real-world production enterprises, where workers are usually partially cross-trained due to high-training costs and employee turnover. However, the hybrid seru system scheduling problem considering worker heterogeneity (HSSWH) has rarely been studied in academia. To fill the gap, this article introduces a branch-and-bound enhanced cooperative evolutionary algorithm (BBCEA) to solve the HSSWH. Three core search components and an evaluation component are proposed in BBCEA, which are crafted to be problem-specific. In the exploration search component, a probability model sampling method and crossover collaborate to generate offspring with high quality and diversity. In the exploitation search component, five knowledge-based operators collaborate with a knowledge-guided operator selection strategy, which is designed by fully utilizing the problem properties and feedback information. In the exact search component, a branch-and-bound method is designed to solve the bottom layer subproblem precisely, which can greatly improve the effectiveness of the algorithm. In the evaluation component, a look-up table method is proposed to reduce computation effort by avoiding duplicate calculations. Numerical experimental results validate the superiority of the BBCEA in addressing the HSSWH, which can obtain the best solution on 95% of the instances compared with the state-of-the-art algorithms.

The rapid expansion of the on-demand food delivery (OFD) market has led the service providers to manage large-scale dynamic order dispatching. Postponing the dispatch of orders is an effective strategy to alleviate the pressures from sudden order surges and to enhance decision-making quality. This paper addresses the OFD problem with order postponement to minimize travel distances and delayed deliveries, focusing on deciding which orders to postpone and which rider to assign for each remaining order at each decision point. We propose a prior and posterior postponement framework that separates the postponement decision-making process into two phases to balance computational efficiency and decision quality. In the prior phase, multiple knowledge-based postponement rules are designed to quickly filter out orders unsuitable for immediate dispatch. In the posterior phase, a data-driven postponement strategy using reinforcement learning is developed to further optimize long-term objectives. Particularly, an action-oriented phase-specific reward shaping method is designed by analyzing the intrinsic nature of the order postponement process, which helps customize the postponement duration for each order to achieve better postponement performance. Extensive numerical ablation and comparative experiments using real-world data demonstrate that the proposed postponement approach is able to improve customer satisfaction, delivery efficiency, and rider experience better than existing methods. Managerial insights are provided regarding the value of order postponement, key factors for designing effective postponement strategies, and practical ready-to-use postponement tactics.

Designing an effective and efficient end-to-end optimization framework with good generalization for shop scheduling is an emerging topic in the informational manufacturing system. Existing end-to-end frameworks have achieved satisfactory results for combinatorial optimization problems (COPs), such as traveling salesman problem and vehicle routing problem. However, the performances of these methods in solving complex COPs, such as shop scheduling, need to be improved. In this article, a knowledge-guided end-to-end optimization framework based on reinforcement learning (RL) is proposed to solve the permutation flow shop scheduling problem (PFSP). First, a new policy network is designed based on the problem characteristics to deal with different scales of PFSPs and achieve iterative end-to-end generation. Second, an improved policy-based RL algorithm by using the knowledge accumulated during the training process is designed to enhance the training quality. Third, a knowledge-guided improvement strategy is introduced through the cooperation of local search and supervised learning to improve the learning of the policy. Simulation results and comparisons show that the knowledge-guided end-to-end optimization framework can obtain better results than different kinds of commonly used optimization methods in limited computation time for solving the PFSP.

As one representative of last-mile logistics in intelligent transportation systems, the on-demand food delivery (OFD) service has gained rapid market growth but also faces multiple challenges. One of the critical issues is the order dispatching problem (ODP) with an NP-hard nature, which refers to dispatching a large number of orders to riders reasonably in real time with very limited decision time. To address the ODP, this paper proposes an optimization algorithm based on graph neural networks (GNN) by combining the advantages of machine learning (ML) techniques and operational research (OR) methods: 1) The ML component learns to reduce the solution space by filtering out inappropriate riders for each order, handling the large-scale complexity of ODP. Specifically, we present a rider modeling approach by using GNN to better characterize rider information; besides, two attention mechanisms are designed to adaptively learn the matching relationship between riders and orders. 2) The OR component ensures the solution quality with a greedy and regret value-based dispatching heuristic. Extensive experiments are conducted on real-world datasets to evaluate the performance of the proposed method by comparing it with other existing models and algorithms. The results show that the design of our ML model is effective in yielding better prediction results, and the proposed GNN-based optimization algorithm can effectively and efficiently solve the ODP by improving delivery efficiency and customer satisfaction.

In many practical manufacturing systems, transportation equipment such as automated guided vehicles (AGVs) is widely adopted to transfer jobs and realize the collaboration of different machines, but is often ignored in current researches. In this article, we address the flexible job shop scheduling problem with finite transportation resources (FJSP-Ts). Considering the difficulties caused by the introduction of transportation and the NP-hard nature, the evolutionary algorithm (EA) is adopted as a solution approach. To this end, a learning-based multipopulation evolutionary optimization (LMEO) is proposed to deal with the FJSP-T. First, the multipopulation strategy is introduced and a cooperation-based initialization is designed by combining several heuristics to guarantee the quality and diversity of the initial population. Second, a reinforcement learning (RL)-based mating selection is proposed to realize the cooperation of different subpopulations by selecting appropriate individuals for evolutionary search. Then, a specific local search inspired by the problem properties is designed to enhance the exploitation capability of the LMEO. Moreover, a statistical learning-based replacement is designed to maintain the quality and diversity of the population. Extensive experiments are conducted to test the performances of the LMEO. The statistical comparison shows that the LMEO is superior to the state-of-the-art algorithms in solving the FJSP-T in terms of solution quality and robustness.

On-demand food delivery (OFD) service is a representative scenario of last-mile logistics. It has gained a fast-growing market but also encounters many challenges, e.g., high dynamism, large-scale complexity, and immediacy requirement. To solve the OFD problem, a predictive-reactive optimization framework with feedback-based knowledge distillation is presented by organically combining deep learning technology and operational research method. In the prediction phase, a deep learning model is designed to predict future information which can reflect the delivery efficiency of dispatching results. To improve model performance, a feedback-based knowledge distillation is proposed which balances the diversity and effectiveness of the ensembled models by adaptively controlling learning weights. In the optimization phase, to avoid myopic decisions and obtain high-quality solutions for long-term objectives, a greedy heuristic with a multi-stage decision-making strategy is designed by employing the predicted future information to assist in making decisions. Extensive experiments are conducted on real-world datasets to test the performance of the proposed model and heuristic. Besides, the simulation results illustrate the superiority of the proposed framework for solving the OFD problem in both delivery efficiency and customer satisfaction.

Online food delivery (OFD) service has developed rapidly due to its great convenience for customers, the enormous markets for restaurants and the abundant job openings for riders. However, OFD platforms are encountering enormous challenges, such as massive demand, inevitable uncertainty and short delivery time. This article addresses an OFD problem with stochastic food preparation time. It is a complex NP-hard problem with uncertainty, large search space, strongly coupled subproblems, and high timeliness requirements. To solve the problem, we design an iterated greedy algorithm with a decomposition-based strategy. Concretely speaking, to cope with the large search space due to massive demands, a filtration mechanism is designed by preliminarily selecting suitable riders. To reduce the risk affected by the uncertainty, we introduce a risk-measuring criterion into the objective function and employ a scenario-sampling method. For timeliness requirements caused by short delivery time, we design two time-saving strategies via mathematical analysis, i.e., an adaptive selection mechanism to choose the method with less computational effort and a fast evaluation mechanism based on the small-scale sampling and machine learning model to speed up evaluation. We also prove an upper bound of the stochastic time cost under risk measurement as one of the baseline features to improve the prediction accuracy. The experiments on real-world data sets demonstrate the effectiveness of the proposed algorithm.

As one representative of the emerging on-demand transport services, the on-demand food delivery (OFD) has penetrated into daily life. Due to its intrinsic complexities, the OFD has attracted the interest of a growing number of logistics researchers. This paper aims at optimizing the OFD process and addresses an OFD problem (OFDP). To overcome the dynamic and large-scale complexity, we abstract the OFDP into a static generalized assignment problem with a rolling horizon strategy. To meet the demand on high service quality and limited computation time, we propose an offline-optimization for online-operation framework based on imitation learning. Under this framework, an imitation learning-enhanced iterated matching algorithm (ILIMA) is proposed, which consists of three basic components: an iterated matching heuristic (IMH) to fast generate solutions, an expert to provide expertise, and a machine learning (ML) model to assist the decision-making process in IMH by mimicking the expert. In the offline-optimization phase, the ML model mines knowledge from the high-quality solutions optimized by the expert; in the online-operation phase, the IMH embedded with the well-trained ML model is deployed online to make decisions in a real OFD scenario. Offline simulation experiments are carried out on real historical data, which validate the superiority of ILIMA compared with existing methods. Moreover, rigorous online A/B tests are conducted on the scheduling system of Meituan, which demonstrates the practical value of ILIMA to improve customer satisfaction and delivery efficiency.

As a scheduling problem with wide application backgrounds, the flow-shop scheduling problem (FSP) in deterministic cases has attracted much attention. However, the neglecting of uncertainty will greatly diminish the application value of scheduling results, which makes it necessary to incorporate the uncertainty in the FSP. In this paper, a fuzzy permutation flow-shop scheduling problem (FPFSP) is considered and a novel evolutionary algorithm with adaptation mechanism (AMEA) is proposed to minimize fuzzy makespan. In the initialization phase, two initialization strategies based on the NEH heuristic are proposed to improve the quality of initial population. In the evolution phase, to enhance the exploitation, multiple local search operators are conducted in a collaborative way where the utilizations of operators are adjusted adaptively according to the feedback of their performances; besides, to save computing resources and balance the exploration and exploitation, the population size is adjusted adaptively with the number of generations. Benchmark instances are generated to evaluate the performance of the AMEA. The experimental results and statistical comparisons show that the proposed algorithm has great advantages in solving the FPFSP.

In recent years, the online food ordering (OFO) platforms have arose fast and brought huge convenience to people in daily life. Under the scenario of a realistic OFO platform, this paper addresses an online meal delivery problem (OMDP). To reduce the search space, the OMDP is decomposed into two sub-problems, i.e., the pickup and delivery problem and the order dispatching problem. To solve each sub-problem effectively, a hybrid differential evolution algorithm is proposed, which is fused by the DE-based phase to plan routes and the heuristic-based phase to determine order dispatching schemes. In the DE-based routing phase, a heuristic considering the urgency of orders is designed to generate the initial population with certain quality. Besides, a mutation operator is developed to enhance the exploration and a crossover operator embedded with local search is designed to enhance the exploitation. In the heuristic-based dispatching phase, a regret heuristic is presented to produce good dispatching solutions by introducing the influences between delivery persons. Numerical tests have been carried out and computational results demonstrate the effectiveness of the proposed algorithm.

Considering the uncertainty in the real world online food delivery applications, this paper addresses an online order dispatching problem with fuzzy preparation times (FOODP). According to the characteristics of the problem, the FOODP is decomposed into two sub-problems, an order assignment problem and a fuzzy traveling salesman problem with pickup and delivery. To deal with the two sub-problems efficiently, a two-stage algorithm is proposed by reasonably fusing a modified greedy search (mGS) and the fruit fly optimization algorithm (FOA). In the mGS phase, agreement index is employed in the multi-stage decision to search for robust optimal solutions. In the FOA-based search phase, a modified heuristic is used to generate the initial route. To enhance the exploration of the algorithm, an olfactory search is designed by the cooperation of several problem-specific search operators. Moreover, a specific local intensification is employed to further improve the performance of solutions. Numerical tests and statistical analysis demonstrate the effectiveness and efficiency of the proposed algorithm.

With the trend of global manufacturing, distributed shop scheduling has been a hot research topic recently. This paper addresses the distributed heterogeneous permutation flow-shop scheduling problem with multiple non-identical factories to minimize makespan. To well solve the problem, a probability model-based memetic algorithm (PMMA) is presented in this paper. Since the non-identical factories have different process capabilities, it is crucial to determine reasonable factory assignment. In PMMA, a probability model is constructed to reflect the probability distribution of factory assignment. At each generation, the probability model is updated by elite individuals to search for good factory assignment scheme. The information from the probability model is extracted and integrated in the designed search operators to help adjusting factory assignment and processing order. Meanwhile, the search operators collaborate to achieve both exploration and exploitation ability. Besides, a local intensification operator is designed to further improve the solution quality. Extensive computational experiments are carried out to test the performance of PMMA. The experiment results demonstrate the effectiveness of the designed PMMA.