A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows

Optimization of heterogeneous vehicle logistics scheduling with multi-objectives and multi-centers

Industrial enterprises have high requirements on timeliness and cost when delivering industrial products to their customers. For this reason, this paper studies the vehicle routing problem (VRP) of different vehicle models in multiple distribution centers. First of all, we consider the multi-dimensional constraints in the actual distribution process such as vehicle load and time window, and build a multi-objective optimization model for product distribution with the goal of minimizing the distribution time and cost and maximizing the loading rate of vehicles. Furthermore, an Improved Life-cycle Swarm Optimization (ILSO) algorithm is proposed based on the life cycle theory. Finally, we use the order data that Yunnan Power Grid Company needs to deliver to the customer (municipal power supply bureau) on a certain day to conduct a dispatching experiment. The simulation and application results show that the transportation cost of transportation obtained by the ILSO algorithm is reduced by 0.8% to 1.6% compared with the other five algorithms. Therefore, ILSO algorithm has advantages in helping enterprises reduce costs and improve efficiency.

Modeling stochastic service time for complex on-demand food delivery

Uncertainty is everywhere in the food delivery process, which significantly influences decision-making for complex on-demand food delivery problems, affecting delivery efficiency and customer satisfaction. Especially, the service time is an indispensable part of the delivery process impacted by various uncertain factors. Due to the simplicity and high accuracy requirement, we model the uncertain service time as a Gaussian mixture model (GMM). In detail, we transform the distribution estimation problem into a clustering problem by determining the probability of each data belonging to each component (each cluster as well). A hybrid estimation of distribution algorithm is proposed to intelligently solve the clustering problem with the criterion to optimize quality and simplicity simultaneously. First, to optimize the simplicity, problem-specific encoding and decoding methods are designed. Second, to generate initial solutions with good clustering results, a Chinese restaurant process-based initialization mechanism is presented. Third, a weighted-learning mechanism is proposed to effectively guide the update of the probability model. Fourth, a local intensification based on maximum likelihood is used to exploit better solutions. The effect of critical parameters on the performances of the proposed algorithm is investigated by the Taguchi design of the experimental method. To demonstrate the effectiveness of the proposed algorithm, we carry out extensive offline experiments on real-world historical data. Besides, we employ the GMMs obtained by our algorithm in a real-world on-demand food delivery platform, Meituan, to assist decision-making for order dispatching. The results of rigorous online A/B tests verify the practical value of introducing the uncertainty model into the real-life application.

Cooperatively Routing a Truck and Multiple Drones for Target Surveillance

With the development of drone technology, drones have been deployed in civilian and military fields for target surveillance. As the endurance of drones is limited, large-scale target surveillance missions encounter some challenges. Based on this motivation, we proposed a new target surveillance mode via the cooperation of a truck and multiple drones, which enlarges the range of surveillance. This new mode aims to rationally plan the routes of trucks and drones and minimize the total cost. In this mode, the truck, which carries multiple drones, departs from its base, launches small drones along the way, surveils multiple targets, recycles all drones and returns to the base. When a drone is launched from the truck, it surveils multiple targets and flies back to the truck for recycling, and the energy consumption model of the drone is taken into account. To assist the new problem-solving, we developed a new heuristic method, namely, adaptive simulated annealing with large-scale neighborhoods, to optimize truck and drone routes, where a scoring strategy is designed to dynamically adjust the selection weight of destroy operators and repair operators. Additionally, extensive experiments are conducted on several synthetic cases and one real case. The experimental results show that the proposed algorithm can effectively solve the large-scale target surveillance problem. Furthermore, the proposed cooperation of truck and drone mode brings new ideas and solutions to targets surveillance problems.

Heterogeneous Multitype Fleet Green Vehicle Path Planning of Automated Guided Vehicle with Time Windows in Flexible Manufacturing System

In this study, we present and discuss a variant of the classical vehicle routing problem (VRP), namely the heterogeneous multitype fleet green automated guided vehicle (AGV) routing problem with time windows (HFGVRPTW) applied in the workshops of flexible manufacturing systems (FMS). Specifically, based on the analysis of AGV body structure and motion state, transport distance and energy consumption are selected as two optimization objectives. According to the characteristics and application context of the problem, this paper designs a hybrid genetic algorithm with large neighborhood search (GA-LNS) considering the farthest insertion heuristic. GA-LNS is improved by increasing the local search ability of genetic algorithm to enhance the solution optimal quality. Extensive computational experiments which are generated from Solomon’s benchmark instances and a real case of FMS are designed to evaluate and demonstrate the efficiency and effectiveness of the proposed model and algorithm. The experimental results reveal that compared with using the traditional homogeneous fleet, the heterogeneous multitype AGV fleet transportation mode has a huge energy-saving potential in workshop intralogistics.