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
- Proactive Depot Discovery: A Generative Framework for Flexible Location-Routing [4.48890356952206]
We propose a data-driven generative DRL framework, designed to proactively generate depots for Location-Routing Problem (LRP)
Our framework can proactively generate depots that lead to superior solution routes with lower routing cost.
The implications of our framework potentially extend into real-world applications, particularly in emergency medical rescue and disaster relief logistics.
arXiv Detail & Related papers (2025-02-17T12:00:28Z) - 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) - 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) - Union-over-Intersections: Object Detection beyond Winner-Takes-All [54.89876370237598]
This paper revisits the problem of predicting box locations in object detection architectures.
We propose a simpler approach: regress only to the area of intersection between the proposal and the ground truth.
Instead of adopting a winner-takes-all strategy, we take the union over the regressed intersections of all boxes in a region to generate the final box outputs.
arXiv Detail & Related papers (2023-11-30T12:40:23Z) - 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.