ﻻ يوجد ملخص باللغة العربية
The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) has attracted much research interest in the last decade, due to its wide application in modern logistics. Since VRPSPDTW is NP-hard and exact methods are only applicable to small-scale instances, heuristics and meta-heuristics are commonly adopted. In this paper we propose a novel Memetic Algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. Compared to existing algorithms, the advantages of MATE lie in two aspects. First, it is capable of more effectively exploring the search space, due to its novel initialization procedure, crossover and large-step-size operators. Second, it is also more efficient in local exploitation, due to its sophisticated constant-time-complexity move evaluation mechanism. Experimental results on public benchmarks show that MATE outperforms all the state-of-the-art algorithms, and notably, finds new best-known solutions on 12 instances (65 instances in total). Moreover, a comprehensive ablation study is also conducted to show the effectiveness of the novel components integrated in MATE. Finally, a new benchmark of large-scale instances, derived from a real-world application of the JD logistics, is introduced, which can serve as a new and more challenging test set for future research.
The Dynamic Vehicle Routing Problem with Time Windows (DVRPTW) is an extension of the well-known Vehicle Routing Problem (VRP), which takes into account the dynamic nature of the problem. This aspect requires the vehicle routes to be updated in an on
The performance of evolutionary algorithms can be heavily undermined when constraints limit the feasible areas of the search space. For instance, while Covariance Matrix Adaptation Evolution Strategy is one of the most efficient algorithms for uncons
Microtransit and other flexible transit fleet services can reduce costs by incorporating transfers. However, transfers are costly to users if they must get off a vehicle and wait at a stop for another pickup. A mixed integer linear programming model
This paper considers the vehicle routing problem of a fleet operator to serve a set of transportation requests with flexible time windows. That is, the operator presents discounted transportation costs to customers to exchange the time flexibility of
On-demand delivery has become increasingly popular around the world. Brick-and-mortar grocery stores, restaurants, and pharmacies are providing fast delivery services to satisfy the growing home delivery demand. Motivated by a large meal and grocery