Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows

• URL: http://arxiv.org/abs/2011.06331v5
• Date: Tue, 8 Jun 2021 08:24:45 GMT
• Title: Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows
• Authors: Shengcai Liu, Ke Tang and Xin Yao
• Abstract summary: We propose a novel Memetic Algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. MATE outperforms all the state-of-the-art algorithms, and notably, finds new best-known solutions on 12 instances (65 instances in total)
• Score: 31.512563458410963
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• BEACON: A Bayesian Optimization Strategy for Novelty Search in Expensive Black-Box Systems [1.204357447396532]
  Novelty search (NS) refers to a class of exploration algorithms that automatically uncover diverse system behaviors through simulations or experiments. We propose a Bayesian optimization inspired algorithm for sample-efficient NS that is specifically designed for such expensive black-box systems. We show that our approach greatly outperforms existing NS algorithms by finding substantially larger sets of diverse behaviors under limited sample budgets.
  arXiv  Detail & Related papers  (2024-06-05T20:23:52Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• AutoSpace: Neural Architecture Search with Less Human Interference [84.42680793945007]
  Current neural architecture search (NAS) algorithms still require expert knowledge and effort to design a search space for network construction. We propose a novel differentiable evolutionary framework named AutoSpace, which evolves the search space to an optimal one. With the learned search space, the performance of recent NAS algorithms can be improved significantly compared with using previously manually designed spaces.
  arXiv  Detail & Related papers  (2021-03-22T13:28:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood [6.85316573653194]
  We introduce a simple -- open-source -- implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP) This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research.
  arXiv  Detail & Related papers  (2020-11-23T21:37:49Z)
• A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem [3.946442574906068]
  This work presents a new meta-heuristic algorithm called GLNSA (Global-local neighborhood search algorithm) The proposed algorithm is complemented with a tabu search that implements a simplified version of the Nopt1 neighborhood. Experiments carried out show a satisfactory performance of the proposed algorithm, compared with other results published in recent algorithms.
  arXiv  Detail & Related papers  (2020-10-23T23:08:51Z)
• Finding Action Tubes with a Sparse-to-Dense Framework [62.60742627484788]
  We propose a framework that generates action tube proposals from video streams with a single forward pass in a sparse-to-dense manner. We evaluate the efficacy of our model on the UCF101-24, JHMDB-21 and UCFSports benchmark datasets.
  arXiv  Detail & Related papers  (2020-08-30T15:38:44Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
  Hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques.
  arXiv  Detail & Related papers  (2019-08-28T13:12:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.