Vehicle routing problem with time windows (VRPTW) contains two crucial objectives: minimizing the number of vehicles and minimizing the total travel distance. However, most algorithms focus on the number of vehicles while the travel distance should be considered as the primary objective in some practical situations especially in the modern logistics. Research has shown that designing a systematic framework to combine multiple algorithms with different characteristics will significantly improve the overall performance of the hybrid algorithm. This paper proposes an evolutionary scatter search particle swarm optimization algorithm(ESS-PSO) to solve the VRPTW with the objective of minimizing the total travel distance. In ESS, a genetic algorithm(GA) and a new "route+/-" evolutionary operator are introduced in scatter search template. Also, we proposed a discrete PSO that sets the route-segment as the velocity of particles and in which the velocity and position updating rules are designed based on the concept of "ruin and recreate." These two algorithms work in a cascade learning architecture in which PSO learns from the exemplary solutions in the reference set maintained by ESS. The search direction of the algorithm is adjusted by analyzing the relationship between the number of vehicles and the total travel distance in real time. We designed a new solution representation called "auxiliary code" based on customer allocation to maintain the diversity of the reference set. Experiments with the Solomon benchmark show that ESS-PSO is effective and efficient, and it achieves very competitive results especially in the datasets of the category "2".
1 January 2019 in Mathematical Problems in Engineering
Robotic mobile fulfilment system (RMFS) is an efficient and flexible order picking system where robots ship the movable shelves with items to the picking stations. This innovative parts‐to‐picker system, known as Kiva system, is especially suited for e‐commerce fulfilment centres and has been widely used in practice. However, there are lots of resource allocation problems in RMFS. The robots allocation problem of deciding which robot will be allocated to a delivery task has a significant impact on the productivity of the whole system. We model this problem as a resource‐constrained project scheduling problem with transfer times (RCPSPTT) based on the accurate analysis of driving and delivering behaviour of robots. A dedicated serial schedule generation scheme and a genetic algorithm using building‐blocks‐based crossover (BBX) operator are proposed to solve this problem. The designed algorithm can be combined into a dynamic scheduling structure or used as the basis of calculation for other allocation problems. Experiment instances are generated based on the characteristics of RMFS, and the computation results show that the proposed algorithm outperforms the traditional rule‐based scheduling method. The BBX operator is rapid and efficient which performs better than several classic and competitive crossover operators.