Optimizing Planning Service Territories by Dividing Into Compact Several
Sub-areas Using Binary K-means Clustering According Vehicle Constraints
- URL: http://arxiv.org/abs/2010.10934v1
- Date: Wed, 21 Oct 2020 12:19:08 GMT
- Title: Optimizing Planning Service Territories by Dividing Into Compact Several
Sub-areas Using Binary K-means Clustering According Vehicle Constraints
- Authors: Muhammad Wildan Abdul Hakim, Syarifah Rosita Dewi, Yurio Windiatmoko,
Umar Abdul Aziz
- Abstract summary: VRP (Vehicle Routing Problem) is an NP hard problem, and it has attracted a lot of research interest.
In this paper we propose new algorithms for producing such clusters/groups that do not exceed vehicles maximum capacity.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: VRP (Vehicle Routing Problem) is an NP hard problem, and it has attracted a
lot of research interest. In contexts where vehicles have limited carrying
capacity, such as volume and weight but needed to deliver items at various
locations. Initially before creating a route, each vehicle needs a group of
delivery points that are not exceeding their maximum capacity. Drivers tend to
deliver only to certain areas. Cluster-based is one of the approaches to give a
basis for generating tighter routes. In this paper we propose new algorithms
for producing such clusters/groups that do not exceed vehicles maximum
capacity. Our basic assumptions are each vehicle originates from a depot,
delivers the items to the customers and returns to the depot, also the vehicles
are homogeneous. This methods are able to compact sub-areas in each cluster.
Computational results demonstrate the effectiveness of our new procedures,
which are able to assist users to plan service territories and vehicle routes
more efficiently.
Related papers
- Exact algorithms and heuristics for capacitated covering salesman problems [0.0]
This paper introduces the Capacitated Covering Salesman Problem (CCSP)
The objective is to service customers through a fleet of vehicles in a depot, minimizing the total distance traversed by the vehicles.
optimization methodologies are proposed for the CCSP based on ILP (Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Routing) metaheuristic.
arXiv Detail & Related papers (2024-03-03T07:50:29Z) - Double-Bounded Optimal Transport for Advanced Clustering and
Classification [58.237576976486544]
We propose Doubly Bounded Optimal Transport (DB-OT), which assumes that the target distribution is restricted within two boundaries instead of a fixed one.
We show that our method can achieve good results with our improved inference scheme in the testing stage.
arXiv Detail & Related papers (2024-01-21T07:43:01Z) - Multi-Agent Learning of Efficient Fulfilment and Routing Strategies in
E-Commerce [11.421159751635667]
paper presents an integrated algorithmic framework for minimising product delivery costs in e-commerce.
One of the major challenges in e-commerce is the large volume of-temporally diverse orders from multiple customers.
We propose an approach that combines graph neural networks and reinforcement learning to train the node selection and vehicle agents.
arXiv Detail & Related papers (2023-11-20T10:32:28Z) - Fair collaborative vehicle routing: A deep multi-agent reinforcement
learning approach [49.00137468773683]
Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other.
Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents.
We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
arXiv Detail & Related papers (2023-10-26T15:42:29Z) - Keypoint-Guided Optimal Transport [85.396726225935]
We propose a novel KeyPoint-Guided model by ReLation preservation (KPG-RL) that searches for the optimal matching.
The proposed KPG-RL model can be solved by Sinkhorn's algorithm and is applicable even when distributions are supported in different spaces.
Based on the learned transport plan from dual KPG-RL, we propose a novel manifold barycentric projection to transport source data to the target domain.
arXiv Detail & Related papers (2023-03-23T08:35:56Z) - 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) - Supervised Permutation Invariant Networks for Solving the CVRP with
Bounded Fleet Size [3.5235974685889397]
Learning to solve optimization problems, such as the vehicle routing problem, offers great computational advantages.
We propose a powerful supervised deep learning framework that constructs a complete tour plan from scratch while respecting an apriori fixed number of vehicles.
In combination with an efficient post-processing scheme, our supervised approach is not only much faster and easier to train but also competitive results.
arXiv Detail & Related papers (2022-01-05T10:32:18Z) - Deep Reinforcement Learning for Solving the Heterogeneous Capacitated
Vehicle Routing Problem [13.389057146418056]
Vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed)
We propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step.
arXiv Detail & Related papers (2021-10-06T10:05:19Z) - A Hybrid Multi-Objective Carpool Route Optimization Technique using
Genetic Algorithm and A* Algorithm [0.0]
This work presents a hybrid GA-A* algorithm to obtain optimal routes for the carpooling problem.
The routes obtained maximize the profit of the service provider by minimizing the travel and detour distance as well as pick-up/drop costs.
The proposed algorithm has been implemented over the Salt Lake area of Kolkata.
arXiv Detail & Related papers (2020-07-11T14:13:20Z) - Key Points Estimation and Point Instance Segmentation Approach for Lane
Detection [65.37887088194022]
We propose a traffic line detection method called Point Instance Network (PINet)
The PINet includes several stacked hourglass networks that are trained simultaneously.
The PINet achieves competitive accuracy and false positive on the TuSimple and Culane datasets.
arXiv Detail & Related papers (2020-02-16T15:51:30Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks.
We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem.
The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
arXiv Detail & Related papers (2020-01-22T08:51:05Z)
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.