A Multi-population Integrated Approach for Capacitated Location Routing

• URL: http://arxiv.org/abs/2403.09361v1
• Date: Thu, 14 Mar 2024 13:11:30 GMT
• Title: A Multi-population Integrated Approach for Capacitated Location Routing
• Authors: Pengfei He, Jin-Kao Hao, Qinghua Wu,
• Abstract summary: This paper presents a multi-population integrated framework for the capacitated location-routing problem. It includes an effective neighborhood-based local search, a feasibility-restoring procedure and a diversification-oriented mutation. Experiments on 281 benchmark instances from the literature show that the algorithm performs remarkably well.
• Score: 14.897794986447474
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The capacitated location-routing problem involves determining the depots from a set of candidate capacitated depot locations and finding the required routes from the selected depots to serve a set of customers whereas minimizing a cost function that includes the cost of opening the chosen depots, the fixed utilization cost per vehicle used, and the total cost (distance) of the routes. This paper presents a multi-population integrated framework in which a multi-depot edge assembly crossover generates promising offspring solutions from the perspective of both depot location and route edge assembly. The method includes an effective neighborhood-based local search, a feasibility-restoring procedure and a diversification-oriented mutation. Of particular interest is the multi-population scheme which organizes the population into multiple subpopulations based on depot configurations. Extensive experiments on 281 benchmark instances from the literature show that the algorithm performs remarkably well, by improving 101 best-known results (new upper bounds) and matching 84 best-known results. Additional experiments are presented to gain insight into the role of the key elements of the algorithm.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem [14.9829752183927]
  The latency location routing problem integrates the facility location problem and the cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations and vehicle routes to serve customers. We propose a reinforcement learning guided hybrid evolutionary algorithm following the framework of the memetic algorithm.
  arXiv  Detail & Related papers  (2024-03-21T13:54:03Z)
• Learning-guided iterated local search for the minmax multiple traveling salesman problem [13.924692115320553]
  We propose a leaning-driven iterated local search approach to the minmax multiple traveling salesman problem. We show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances.
  arXiv  Detail & Related papers  (2024-03-19T02:57:10Z)
• Competitive Facility Location under Random Utilities and Routing Constraints [4.9873153106566575]
  We study a facility location problem within a competitive market context, where customer demand is predicted by a random utility choice model. We introduce routing constraints that necessitate the selection of locations in a manner that guarantees the existence of a tour visiting all chosen locations.
  arXiv  Detail & Related papers  (2024-03-07T06:56:24Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Learning Space Partitions for Path Planning [54.475949279050596]
  PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
  arXiv  Detail & Related papers  (2021-06-19T18:06:11Z)
• Sparse Reward Exploration via Novelty Search and Emitters [55.41644538483948]
  We introduce the SparsE Reward Exploration via Novelty and Emitters (SERENE) algorithm. SERENE separates the search space exploration and reward exploitation into two alternating processes. A meta-scheduler allocates a global computational budget by alternating between the two processes.
  arXiv  Detail & Related papers  (2021-02-05T12:34:54Z)
• Exploration in two-stage recommender systems [79.50534282841618]
  Two-stage recommender systems are widely adopted in industry due to their scalability and maintainability. A key challenge of this setup is that optimal performance of each stage in isolation does not imply optimal global performance. We propose a method of synchronising the exploration strategies between the ranker and the nominators.
  arXiv  Detail & Related papers  (2020-09-01T16:52:51Z)

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.