#### 論文の概要、ライセンス

 # (参考訳) 再帰的KMeansとDijkstraアルゴリズムによるCVRPの解法 [全文訳有] Using Recursive KMeans and Dijkstra Algorithm to Solve CVRP ( http://arxiv.org/abs/2102.00567v1 ) ライセンス: CC BY 4.0 Hassan Moussa (参考訳) キャパシタ付き車両ルーティング問題(CVRP)は、今日の最も一般的な最適化問題のひとつです。 Capacitated vehicle routing problem (CVRP) is being one of the most common optimization problems in our days 公開日: Mon, 1 Feb 2021 00:03:03 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

#### 翻訳結果

Page: /

Using Recursive KMeans and Dijkstra Algorithm to Solve CVRP 再帰的KMeansとDijkstraアルゴリズムによるCVRPの解法 0.79
Author: Hassan Moussa 著者:Hassan Moussa 0.70
*Lebanese University, Department of applied ※レバノン大学応用学科 0.51
mathematics* Abstract: Capacitated vehicle routing problem (CVRP) is being one of the most common optimization problems in our days, considering the wide usage of routing algorithms in multiple fields such as transportation domain, food delivery, network routing, ... Capacitated vehicle routing problem is classified as an NP-Hard problem, hence normal optimization algorithm can’t solve it. 数学* 概要 キャパシタン化車両ルーティング問題(CVRP)は、輸送領域、フードデリバリー、ネットワークルーティングといった複数の分野におけるルーティングアルゴリズムの幅広い利用を考えると、現在最も一般的な最適化問題の1つであり、キャパシタン化車両ルーティング問題はNP-Hard問題に分類されているため、通常の最適化アルゴリズムでは解決できない。 0.59
In our paper, we discuss a new way to solve the mentioned problem, using a recursive approach of the most known clustering algorithm “K-Means”, one of the known shortest path algorithm “Dijkstra”, and some mathematical operations. 本稿では、既知の最短経路アルゴリズム「Dijkstra」の1つであるクラスタリングアルゴリズム「K-Means」の帰納的アプローチと、いくつかの数学的操作を用いて、前述の問題を解決する新しい方法について議論する。 0.84
In this paper, we will show how to implement those methods together in order to get the nearest solution of the optimal route, since research and development are still on go, this research paper may be extended with another one, that will involve the implementational results of this thoric side. 本稿では, 最適な経路の最も近い解を得るために, それらの手法をどのように実装するかを示す。研究と開発はまだ進行中であるので, 本研究論文を他の方法とともに拡張して, この胸側の実装結果を取り込むことができる。 0.79
Keywords: VRP, CVRP, artificial intelligence, capacitated vehicle routing optimization, unsupervised machine learning. キーワード: vrp, cvrp, artificial intelligence, capacitated vehicle routing optimization, unsupervised machine learning。 0.81
routing algorithm, ルーティングアルゴリズム。 0.65
routing problem, I. ルーティングの問題 私。 0.69
Introduction: Capacitated vehicle routing problem is finding the optimal route for a fleet of vehicles to pass through a number of clients, given a set of constraints. 序文 容量の確保された車両ルーティング問題は、一連の制約により、車両群が複数のクライアントを通過するのに最適な経路を見つけることである。 0.45
The CSVP was very extremely studied in the field of optimization, because of its wide uses, and the whole evolution in the E-commerce and delivery field, also the spread of school and taxi operators. CSVPは、その幅広い用途、およびEコマースおよび配送分野での全体的な進化、また学校やタクシー事業者の広がりのために、最適化の分野で非常に研究されました。 0.73
Capacitated vehicle routing problem is a subset of vehicle routing problem (VRP) which is very common, キャパシタ付き車両ルーティング問題は、非常に一般的である車両ルーティング問題(VRP)のサブセットです。 0.72
CVRP is related to the size of vehicle, which is considered as a constraint. CVRPは、制約と見なされる車両のサイズに関連しています。 0.71
In other words, VRP is the problem of finding the least cost of routes from a depot to a set of geographical points. 言い換えれば、VRPは、デポから地理的なポイントのセットへのルートの最小コストを見つけることの問題です。 0.61
In order to define the capacitated vehicle routing problem in mathematical terms we will start by defining some parameters: 容量化車両ルーティング問題を数学的に定義するために、いくつかのパラメータを定義することから始める。 0.69
n is the number of clients nはクライアントの数です 0.79
• N is set of clients, with N= {1,2, …, n} • V is set of nodes with V = {0} ∪ N • A is a set of arcs, with A = { (𝑖, 𝑗) ∈ 𝑉2 ∶ 𝑖 ≠ 𝑗 } • 𝐶𝑖𝑗 𝑖𝑠 𝑡ℎ𝑒 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑡𝑟𝑎𝑣𝑒𝑙 𝑜𝑣𝑒𝑟 𝑎𝑟𝑐 (𝑖, 𝑗) ∈ 𝐴 • 𝑄 𝑖𝑠 𝑡ℎ𝑒 𝑣𝑒ℎ𝑖𝑐𝑙𝑒 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 • N はクライアントの集合であり、N = {1,2, ..., n} • V はノードの集合であり、V = {0} > N • A はアークの集合であり、A = { (i, j) ∈ V2 > i > j } • Cij はアーク(i, j) ∈ A • Q は車両容量である。 0.80
Figure 1: Graph of CVRP / https://neo.lcc.uma. es/dynamic/images/vr p.png 図1:CVRP / https://neo.lcc.uma. es/dynamic/images/vr p.png 0.43
The formulation in terms of mathematical operation will be: 数学的操作の項の定式化は次のようになる。 0.54
min 𝑖,𝑗∈ 𝐴 ∑ 𝑐𝑖𝑗 𝑖,𝑗 ∈𝐴 min i,j∈A ∑ 𝑐𝑖𝑗 𝑖,𝑗 ∈𝐴 0.96
𝑥𝑖𝑗 Which mean that we need to minimize the whole cost. 𝑥𝑖𝑗 つまり、全体のコストを最小限に抑える必要があります。 0.78
∑ 𝑥𝑖𝑗 = 1 𝑤ℎ𝑖𝑙𝑒 𝑖 ∈ 𝑁 ∑ 𝑥𝑖𝑗 = 1 𝑤ℎ𝑖𝑙𝑒 𝑖 ∈ 𝑁 0.88
𝑗 ∈ 𝑉 ,𝑗 ≠ 𝑖 𝑗 ∈ 𝑉 ,𝑗 ≠ 𝑖 0.85
if x is a client then it should belong to one node, and go only to one node. x がクライアントであれば、1つのノードに属し、1つのノードにのみ行きます。 0.82
∑ 𝑥𝑖𝑗 = 1 𝑤ℎ𝑖𝑙𝑒 𝑖 ∈ 𝑁 ∑ 𝑥𝑖𝑗 = 1 𝑤ℎ𝑖𝑙𝑒 𝑖 ∈ 𝑁 0.88
𝑖 ∈ 𝑉 ,𝑖 ≠ 𝑗 𝑖 ∈ 𝑉 ,𝑖 ≠ 𝑗 0.85
If I reach a client, then I should come from another node. もしクライアントに到達したら、別のノードから来るべきです。 0.71
pg. 1 Hassan Moussa 2021 pg。 1 Hassan Moussa 2021 0.83

II. Method: The CVRP problem can be divided into multiple subproblems, in our paper we will follow the following approach: II。 方法 cvrp問題は複数のサブプロブレムに分けられるが、本論文では以下のアプローチに従う。

0.64
1. Finding the optimal distribution of students along the vehicles, their capacity, this will help the algorithm in optimizing the overall occupacity 1. 車両沿いの学生の最適分布とその能力を見出すことは、全体の占有力を最適化するアルゴリズムに役立ちます。 0.83
into consideration taking 2. 考慮して テイク 2. 0.68
Clustering the clients into a number of clusters that suits the number of vehicles and their capacity using our recursive approach of “K-Means” algorithm, and then assign each cluster to a vehicle, taking into consideration the occupacity of the vehicle, the ride time, and the ride distance. K-Means」アルゴリズムの再帰的なアプローチを使用して、車両の数とその容量に合ったいくつかのクラスタにクライアントをクラスタ化し、車両の占有率、乗車時間、および乗車距離を考慮して、各クラスタを車両に割り当てます。 0.73
3. Performing a second phase of optimization, this phase will make sure that the occupacity of a vehicle is optimal taking into consideration the ride distance and time, in case any of our constraints is touched, we go through a hierarchical clustering to join or split a specific cluster. 3. 最適化の第2段階を実行すると、このフェーズでは、乗車距離と時間を考慮して車両の占有率が最適であることを確認します。

0.78
4. Performing the routing between each node of the cluster and the most near one, and then between the depot ({0}) and the nearest node of a cluster, in our approach, we are using an open shortest path algorithm “Dijkstra”, we represent the considered city or country as a mathematical graph, where every location is a vertex, and the existence of a route between any 2 vertices is considered as an edge, using “Dijkstra” we can find the shortest path to travel through all nodes. 4. Performing the routing between each node of the cluster and the most near one, and then between the depot ({0}) and the nearest node of a cluster, in our approach, we are using an open shortest path algorithm “Dijkstra”, we represent the considered city or country as a mathematical graph, where every location is a vertex, and the existence of a route between any 2 vertices is considered as an edge, using “Dijkstra” we can find the shortest path to travel through all nodes. 0.85
𝑥 ∈ 𝑅𝑛 , 𝑥 = 𝑥 ∈ 𝑅𝑛 , 𝑥 = 0.85
𝑥1 ⋮ 𝑥𝑡 𝑥1 ⋮ 𝑥𝑡 0.94
𝑥𝑖 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑣𝑖 𝑛𝑒𝑒𝑑𝑒𝑑 , 0 ≤ 𝑖 ≤ 𝑡 𝑥𝑖 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑣𝑖 𝑛𝑒𝑒𝑑𝑒𝑑 , 0 ≤ 𝑖 ≤ 𝑡 0.85
The final equation to find the optimal number of each vehicle needed is: 各車両の最適数を求める最後の方程式は次のとおりである。 0.76
𝑓(𝑥) = 𝑛 Known that: 𝑓(𝑥) = 𝑛 ご存知の通り 0.64
𝑡 𝑓(𝑥) = ∑ 𝑥𝑖𝑐𝑖 𝑡 𝑓(𝑥) = ∑ 𝑥𝑖𝑐𝑖 0.85
= 𝑥1𝑐1 + 𝑥2𝑐2 + ⋯ + 𝑥𝑡𝑐𝑡 = 𝑥1𝑐1 + 𝑥2𝑐2 + ⋯ + 𝑥𝑡𝑐𝑡 0.71
𝑖=1 f(x) is a defined function 𝑅𝑛 → 𝑅 , which find the number of each vehicle needed x, taking into consideration that the sum of the combination between the capacity and number of vehicles assigned should equal to the total number of clients. 𝑖=1 f(x) は定義された関数 Rn → R であり、割り当てられた車両の容量と数の組み合わせの合計がクライアントの総数に等しいべきであることを考慮に入れて、必要な各車両の数を見つける。 0.72
In order to find x, we are going to use one of known method in numerical analysis, “Newton-Raphson Method” applied to n variables. xを見つけるために、n変数に適用される数値解析に既知の方法の1つ「Newton-Raphson Method」を使用します。 0.85
Objective: find an approximation of the equation 𝑓(𝑥) = 𝑛 → 𝑓(𝑥) − 𝑛 = 0 目的:方程式 f(x) = n → f(x) − n = 0 の近似を求める。 0.80
Input: • 𝐹 ∶ 𝑅𝑛 → 𝑅 • 𝐽𝑎𝑐𝑜𝑏𝑖𝑎𝑛𝑒 𝑀𝑎𝑡𝑟𝑖𝑐𝑒 𝐽𝑓 ∶ 𝑅𝑛 → 𝑅𝑛 • A first approximation 𝑋0 ∈ 𝑅𝑛 • The precision required 𝜀 ∈ 𝑅 , 𝜀 > 0 入力: • 𝐹 ∶ 𝑅𝑛 → 𝑅 • 𝐽𝑎𝑐𝑜𝑏𝑖𝑎𝑛𝑒 𝑀𝑎𝑡𝑟𝑖𝑐𝑒 𝐽𝑓 ∶ 𝑅𝑛 → 𝑅𝑛 • A first approximation 𝑋0 ∈ 𝑅𝑛 • The precision required 𝜀 ∈ 𝑅 , 𝜀 > 0 0.82
A. Optimal distribution of students in vehicles: a. 車両における学生の最適分布 0.83
Output: Vehicles in Capacitated Vehicle Routing problem can have a specific capacity, each vehicle can differ from others, which will be directly related to an important insight, the “Occupacity”, one of our algorithm KPI, so in order to build the perfect solution we need to start by finding the best distribution of clients. 出力: Capacitated Vehicle Routing問題の車両は、特定の容量を持つことができ、各車両は、重要な洞察、私たちのアルゴリズムKPIの1つ「稼働率」に直接関連している他の車両と異なる場合がありますので、クライアントの最高の分布を見つけることから始める必要がある完璧なソリューションを構築するために。 0.77
Let’s start by defining the problem in mathematical terms, let’s consider that we have t number of vehicles, and n the number of clients. まずは数学用語で問題を定義することから始め、t車両数、nクライアント数を考えてみましょう。

0.56
𝑉 = {𝑣1 , 𝑣2 , … , 𝑣𝑡 } 𝑠𝑒𝑡 𝑜𝑓 𝑡 𝑣𝑒ℎ𝑖𝑐𝑙𝑒𝑠 𝑉 = {𝑣1 , 𝑣2 , … , 𝑣𝑡 } 𝑠𝑒𝑡 𝑜𝑓 𝑡 𝑣𝑒ℎ𝑖𝑐𝑙𝑒𝑠 0.94
𝐶 = {𝑐1 , 𝑐2 , … , 𝑐𝑡 } 𝑠𝑒𝑡 𝑜𝑓 𝑎𝑠𝑠𝑖𝑔𝑛𝑒𝑑 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 𝐶 = {𝑐1 , 𝑐2 , … , 𝑐𝑡 } 𝑠𝑒𝑡 𝑜𝑓 𝑎𝑠𝑠𝑖𝑔𝑛𝑒𝑑 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑦 0.96
𝑐𝑖 = 𝐶𝑎𝑝𝑎𝑐𝑖𝑡𝑦(𝑣𝑖) 𝑓𝑜𝑟 1 ≤ 𝑖 ≤ 𝑡 𝑐𝑖 = 𝐶𝑎𝑝𝑎𝑐𝑖𝑡𝑦(𝑣𝑖) 𝑓𝑜𝑟 1 ≤ 𝑖 ≤ 𝑡 0.85
An approximation of the solution 𝑥∗ ∈ 𝑅𝑛 解 x∗ ∈ Rn の近似 0.63
Initialization: Iterations: 初期化 イテレーション: 0.68
𝛼 = 0 𝑑𝛼+1 = 𝛼 = 0 𝑑𝛼+1 = 0.78
−𝐹(𝑥𝛼) 𝐽𝑓(𝑥𝛼) −𝐹(𝑥𝛼) 𝐽𝑓(𝑥𝛼) 0.94
𝐽𝑓(𝑥𝛼) = ( 𝐽𝑓(𝑥𝛼) = ( 0.85
𝜕𝑓 𝜕𝑥1 (𝑥𝛼) , 𝜕𝑓 𝜕𝑥1 (𝑥𝛼) , 0.87
𝜕𝑓 𝜕𝑥2 (𝑥𝛼), … . 𝜕𝑓 𝜕𝑥2 (𝑥𝛼), … . 0.81
𝜕𝑓 𝜕𝑥𝑡 (𝑥𝛼) ) 𝜕𝑓 𝜕𝑥𝑡 (𝑥𝛼) ) 0.85
Set: 𝑥𝛼+1 = 𝑥𝛼 + 𝑑𝛼+1 Set: 𝑥𝛼+1 = 𝑥𝛼 + 𝑑𝛼+1 0.78
Set: α = α + 1 Set: α = α + 1 0.85
Stop When: ‖𝐹(𝑥𝛼)‖ ≤ 𝜀 → 𝑥∗ = 𝑥𝛼 停止時: F(xα) ≤ ε → x* = xα 0.90
pg. 2 Hassan Moussa 2021 pg。 2 Hassan Moussa 2021 0.83

𝑥∗ is a distribution approximation of the clients and vehicles, so we need 𝑥1 number vehicles 𝑣1 of capacity 𝑐1. x∗ はクライアントと車両の分布近似であるため、容量 c1 の x1 番車 v1 が必要です。 0.77
Algorithm: Consider 𝑐1 , 𝑐2 , . アルゴリズム: Consider 𝑐1 , 𝑐2 , . 0.82
. , 𝑐𝑘 k random centroid . ck k ランダム中心体 0.74
B. Recursive Clustering “K-Means”: B.再帰クラスタリング「K-Means」 0.71
Clustering in one of the most important phases of any routing algorithm, because it will affect directly the final results and KPIs of our algorithm, in our approach, we are clustering our clients in a recursive approach, we start by dividing the client’s data in two clusters based on their geolocation, and then we apply the same “K-Means” again on the two clusters, until we reach the threshold, which will be one of the vehicle capacity, in this case, this cluster will be assigned to this vehicle. Clustering in one of the most important phases of any routing algorithm, because it will affect directly the final results and KPIs of our algorithm, in our approach, we are clustering our clients in a recursive approach, we start by dividing the client’s data in two clusters based on their geolocation, and then we apply the same “K-Means” again on the two clusters, until we reach the threshold, which will be one of the vehicle capacity, in this case, this cluster will be assigned to this vehicle. 0.87
Each iteration of the recursive “K-Means” is saved in a phase tree, the root phase will be the initial data, then the phase 2 and 3 will be the left and right nodes represented as clusters. 再帰的な“k-means”の各イテレーションはフェーズツリーに保存され、ルートフェーズは初期データとなり、フェーズ2と3はクラスタとして表現される左ノードと右ノードとなる。 0.75
N clients Phase N クライアント 段階 0.75
Root Phase Phase Repeat Until Done: 根 段階 段階 完了するまで繰り返す。 0.63
For each 𝑥𝑖 : 1.Get nearest centroid 𝑐𝑗: 各xiについて: 1. 最寄りのセントロイド cj: 0.64
𝑎𝑟𝑔 min 𝑗 𝐷(𝑥𝑖 , 𝑐𝑗) アルグミン 𝑗 𝐷(𝑥𝑖 , 𝑐𝑗) 0.66
2.Assign 𝑥𝑖 to 𝑐𝑗 2. xi を cj に割り当てる 0.64
3. for each cluster j = 1,2, …, k 3. 各クラスタ j = 1,2, ..., k に対して 0.79
Get the new center: 新しいセンターを取得します。 0.66
𝑐𝑒𝑛𝑡𝑒𝑟 = 1 𝑛𝑗 𝑐𝑒𝑛𝑡𝑒𝑟 = 1 𝑛𝑗 0.85
∑ 𝑥𝑖𝐷(𝑥𝑖 , 𝑐𝑗) ∑ 𝑥𝑖𝐷(𝑥𝑖 , 𝑐𝑗) 0.85
The algorithm will first set a random centroid, assign nodes to the nearest one, then calculate the new center, and assign nodes to new centroid. アルゴリズムはまずランダムなセントロイドを設定し、最も近いものにノードを割り当て、次に新しいセンターを計算し、新しいセントロイドにノードを割り当てます。 0.74
Iterating over this operation until nodes are assigned to the same centroid. ノードが同じcentroidに割り当てられるまで、この操作を繰り返す。 0.71
Because we are dealing with geolocations, we are using haversine as a distance function, which can be defined as the following: 位置決めを扱うため、距離関数としてハスリンを用いており、次のように定義できる。

0.56
n/2 111111111 1 n/2 111111111 1 0.72
n/2 2 n/2 2 0.72
2: Figure images.githubusercon tent.com/2789198/272 40436e9a459da-52d4-1 1e7-8f84-f96d0b31285 9.png 2: 画像.githubusercontent.c om/2789198/27240436e 9a459da-52d4-11e7-8f 84-f96d0b312859.png 0.47
Haversine Formula, https://user- ハヴェルシン 公式 https://user- 0.50
Let’s start by defining the K-Means algorithm, the objective function of this algorithm can de represented in the following shape: K-Meansアルゴリズムを定義することから始めましょう。このアルゴリズムの客観的関数は次の形で表現できます。 0.73
Regarding the time complexity of this algorithm, lets consider that our algorithm iterates n times, have k cluster, w nodes and d dimensions, so the complexity of the regular “K-Means” is: このアルゴリズムの時間複雑性について、アルゴリズムがn回反復し、kクラスタ、wノード、d次元を持つので、通常の「k平均」の複雑さは次のようになる。 0.77
𝑂(𝑛 ∗ 𝑘 ∗ 𝑤 ∗ 𝑑) 𝑂(𝑛 ∗ 𝑘 ∗ 𝑤 ∗ 𝑑) 0.85
𝑘 𝑛 𝐽 = ∑ ∑‖𝑥(𝑗) 𝑘 𝑛 𝐽 = ∑ ∑‖𝑥(𝑗) 0.89
2 𝑖 − 𝑐𝑗‖ 2 𝑖 − 𝑐𝑗‖ 0.98
𝑗=1 𝑖=1 In our case, we will split each cluster into 2, and we are working on 2 dimensions, so the complexity will be for an iteration of recursive “K-means”: 𝑗=1 𝑖=1 この場合、各クラスタを2に分割し、2次元に取り組んでいるので、複雑さは再帰的な「K-means」の繰り返しになります。 0.64
Where: k is number of clusters, n is number of cases, we will define the algorithm step by step in the following: k がクラスタ数、n がケース数である場合、次のようにアルゴリズムをステップバイステップで定義する。

0.75
Input: k number of clusters, 𝑥1 , 𝑥2 , … , 𝑥𝑛 n elements to be clustered 入力: k 個のクラスタ x1 , x2 , ... , xn n 要素をクラスタ化する。 0.81
pg. 3 𝑂(4 ∗ 𝑛 ∗ 𝑤) pg。 3 𝑂(4 ∗ 𝑛 ∗ 𝑤) 0.83
After having defined the regular “K-Means” clustering algorithm, we will go to implement our approach used in geolocation data, which is the recursive “K-Means” 通常の「K-Means」クラスタリングアルゴリズムを定義した後、再帰的な「K-Means」である位置情報データで使用されるアプローチを実装します。 0.75
Hassan Moussa 2021 Hassan Moussa 2021 0.85

Input: D- Routing Phase using “Dijkstra”: 入力: D- Routing Phase using "Dijkstra": 0.80
Root Phase (initial dataset of geolocation) ルートフェイズ(位置推定の初期データセット) 0.73
Algorithm: • 𝑐1 , 𝑐2 = 𝐾𝑚𝑒𝑎𝑛𝑠(𝑟𝑜𝑜𝑡) • 𝑟𝑜𝑜𝑡. アルゴリズム: • 𝑐1 , 𝑐2 = 𝐾𝑚𝑒𝑎𝑛𝑠(𝑟𝑜𝑜𝑡) • 𝑟𝑜𝑜𝑡. 0.85
𝑟𝑖𝑔ℎ𝑡 = 𝑐1 • 𝑟𝑜𝑜𝑡. 𝑟𝑖𝑔ℎ𝑡 = 𝑐1 • 𝑟𝑜𝑜𝑡. 0.82
𝑙𝑒𝑓𝑡 = 𝑐2 • 𝐾𝑀𝑒𝑎𝑛𝑠(𝑟𝑜𝑜𝑡. 𝑙𝑒𝑓𝑡 = 𝑐2 • 𝐾𝑀𝑒𝑎𝑛𝑠(𝑟𝑜𝑜𝑡. 0.94
𝑟𝑖𝑔ℎ𝑡) • 𝐾𝑀𝑒𝑎𝑛𝑠(𝑟𝑜𝑜𝑡. 𝑟𝑖𝑔ℎ𝑡) • 𝐾𝑀𝑒𝑎𝑛𝑠(𝑟𝑜𝑜𝑡. 0.94
𝑙𝑒𝑓𝑡) Stop Case: 𝑙𝑒𝑓𝑡) ストップケース: 0.76
The number of nodes assigned to a cluster is equal to one of our vehicle capacities 𝑥∗, stop iterating through this cluster and assign it to the mentioned vehicle. クラスタに割り当てられたノードの数は、当社の車両容量の 1 つ x と等しく、このクラスタの繰り返しを停止し、前述の車両に割り当てます。 0.77
Output: We know that in the geolocation world, there is an infinity of route to go from a geolocation to another, and because we are dealing with vehicles, we restrict our research on the optimal driving route between two location. 出力: 位置情報の世界では、ジオロケーションから別の場所に移動するルートの無限性があり、車両を扱うため、2つの場所の間の最適な運転ルートの研究を制限しています。 0.73
The recent output was an optimized cluster that involve nearest nodes, now we need to set a flow to know where to start and where to finish, and taking into consideration that the covering route for all nodes should be optimal. 最近の出力は、最も近いノードを含む最適化されたクラスタでした。今は、開始場所と終了場所を知るためのフローを設定し、すべてのノードのカバールートが最適であることを考慮する必要があります。 0.74
We will start by considering the concerned city or country as a graph, where each location is a vertex, and a driving route between two location is considered as an edge, lets start by defining this graph: まず、関連する都市または国をグラフとして考慮し、各場所が頂点であり、2つの場所の間の運転ルートがエッジとみなされ、このグラフを定義することから始めます。 0.79
𝑉 = {𝑣1, 𝑣2 , … , 𝑣𝑛 } 𝑠𝑒𝑡 𝑜𝑓 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 (𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛𝑠) 𝑉 = {𝑣1, 𝑣2 , … , 𝑣𝑛 } 𝑠𝑒𝑡 𝑜𝑓 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 (𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛𝑠) 0.94
All leaves of the tree are the final result of our algorithm, they will be the clusters to be applied to routing algorithm later. 木の葉はすべてアルゴリズムの最終結果であり、後にルーティングアルゴリズムに適用されるクラスタとなるでしょう。

0.72
𝐸 ⊆ {{𝑥, 𝑦} 𝑥, 𝑦 ∈ 𝑉 𝑎𝑛𝑑 𝑥 ≠ 𝑦 } 𝐸 ⊆ {{𝑥, 𝑦} 𝑥, 𝑦 ∈ 𝑉 𝑎𝑛𝑑 𝑥 ≠ 𝑦 } 0.85
C-Optimization Phase: C-Optimization フェーズ: 0.75
After getting the final clusters by our recursive algorithm, some clusters may have a low number of assigned nodes, which may affect the over all occupacity rate, this is the reason of the optimization phase, it looks into all clusters, and see where we can edit to optimize the final KPIs, we take a parameter which is the minimum percentage of a cluster, if a cluster doesn’t fit the minimum, we start by looking to other clusters who can handle the number of nodes available on it. After getting the final clusters by our recursive algorithm, some clusters may have a low number of assigned nodes, which may affect the over all occupacity rate, this is the reason of the optimization phase, it looks into all clusters, and see where we can edit to optimize the final KPIs, we take a parameter which is the minimum percentage of a cluster, if a cluster doesn’t fit the minimum, we start by looking to other clusters who can handle the number of nodes available on it. 0.85
This is done by calculating the distance between the centroid of the low occupacity cluster and the available others, and merge the nearest one. これは、低占有率クラスタのセントロイドと利用可能な他のものの間の距離を計算し、最も近いものをマージすることによって行われる。 0.57
This is a mathematical operation to get the following value: これは以下の値を得るための数学的操作である。 0.75
min ‖𝐷(𝑐𝑖 − 𝑐𝑗‖ 分 ‖𝐷(𝑐𝑖 − 𝑐𝑗‖ 0.72
𝑗 Which is the minimum distance between the centroid i of the affected cluster and all other available cluster. 𝑗 影響を受けるクラスタのセントロイド i と利用可能な他のすべてのクラスタの間の最小距離です。 0.80
Note: a cluster is considered available if: 注意: クラスターは以下の場合に利用できます。 0.69
𝑛𝑗 + 𝑛𝑖 < 𝑐𝑗 which means that the nodes available on cluster j added to the one on cluster i are still under the over all capacity of the vehicle. nj + ni < cj は、クラスタ j で利用可能なノードがクラスタ i 上のノードに追加されることを意味する。 0.59
After the optimization phase, the most important part takes the initiative, “Routing Phase” which will take the responsibility of finding the optimal routing in a cluster. 最適化フェーズの後、最も重要な部分は、クラスタ内で最適なルーティングを見つける責任を負う“ルーティングフェーズ”というイニシアチブを取ります。 0.60
pg. 4 Figure 3 Example of a graph applied on geo location data https://miro.medium. com/max/1766/0*18Kbd JeKuUBYm8 JR pg。 4 図3 位置情報データhttps://miro.medium. com/max/1766/0*18Kbd JeKuUBYm8 JRに適用したグラフの例。 0.73
Applying “Dijkstra” in the given graph: グラフに “Dijkstra” を適用する。 0.72
Input: Graph G and the source node 入力: Graph G とソースノード。 0.77
Algorithm: Set: 𝑑𝑖𝑠𝑡[𝑠𝑜𝑢𝑟𝑐𝑒] = 0 アルゴリズム: set: dist[source] = 0 0.76
𝐶𝑜𝑛𝑠𝑖𝑑𝑒𝑟 𝑄 𝑎𝑠 𝑎 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 𝑞𝑢𝑒𝑢𝑒 𝐶𝑜𝑛𝑠𝑖𝑑𝑒𝑟 𝑄 𝑎𝑠 𝑎 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 𝑞𝑢𝑒𝑢𝑒 0.85
Hassan Moussa 2021 Hassan Moussa 2021 0.85

For each vertex v in Graph: グラフの各頂点 v について: 0.81
Time Complexity Study: If v ≠ source: 時間複雑性の研究: ソースが v の場合。 0.76
𝑑𝑖𝑠𝑡[𝑣] = ∞ 𝑑𝑖𝑠𝑡[𝑣] = ∞ 0.85
𝑝𝑟𝑒[𝑣] = 𝑢𝑛𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑝𝑟𝑒[𝑣] = 𝑢𝑛𝑑𝑒𝑓𝑖𝑛𝑒𝑑 0.85
𝑄 ← (𝑣 , 𝑑𝑖𝑠𝑡(𝑣)) 𝑄 ← (𝑣 , 𝑑𝑖𝑠𝑡(𝑣)) 0.85
While Q is not empty: 𝑢 ← min (𝑄) Q は空でないが: 約1分(Q)。 0.61
For each neighbor v of u: u の各隣人 v に対して。 0.65
𝑎𝑙𝑡 ← 𝑑𝑖𝑠𝑡[𝑢] + 𝑙𝑒𝑛(𝑢, 𝑣) 𝑎𝑙𝑡 ← 𝑑𝑖𝑠𝑡[𝑢] + 𝑙𝑒𝑛(𝑢, 𝑣) 0.85
If alt < 𝑑𝑖𝑠𝑡[𝑣] : alt < dist[v] の場合。 0.75
𝑑𝑖𝑠𝑡[𝑣] ← 𝑎𝑙𝑡 𝑑𝑖𝑠𝑡[𝑣] ← 𝑎𝑙𝑡 0.85
𝑝𝑟𝑒𝑣[𝑣] ← 𝑢 𝑝𝑟𝑒𝑣[𝑣] ← 𝑢 0.85
Output: Distance and previous. 出力: 距離と前もって 0.77
So, the routing algorithm will be defined as follow: したがって、ルーティングアルゴリズムは次のように定義されます。 0.71
Input: clusters Algorithm: 入力:クラスタ アルゴリズム: 0.73
For each cluster c: 各クラスタ c のため。 0.77
Add cluster nodes to the geo graph. ジオグラフにクラスタノードを追加します。 0.78
For each node n in cluster: クラスタ内の各ノード n について: 0.78
Apply Dijkstra to get the nearest node regarding the driving distance, add it to a list. Dijkstraを適用して、運転距離に関する最も近いノードを取得し、リストに追加する。 0.83
(Node 1, Node 3). (Node 1, Node 3)。 0.79
Delete Node 1 from the iterator. イテレーターからNode 1を削除します。 0.71
Iterate through all nodes. すべてのノードを繰り返す。 0.78
Append {0} to the list Append {0} to the list 0.85
Iterate through all clusters すべてのクラスタを反復する 0.71
Output: 𝑛𝑖 𝑐 ∑ ∑ 𝑜(|𝑛𝑖|. 出力: 𝑛𝑖 𝑐 ∑ ∑ 𝑜(|𝑛𝑖|. 0.87
𝑇𝑑𝑘 + 𝑂(2. 𝑛𝑖). 𝑇𝑑𝑘 + 𝑂(2. 𝑛𝑖). 0.94
𝑇𝑒𝑚) 𝑖=1 𝑇𝑒𝑚) 𝑖=1 0.78
𝑗=1 Where c is the number of clusters, 𝑗=1 c がクラスタの数である場合。 0.67
𝑛𝑖 is the number of nodes in the cluster i niはクラスタIのノード数です 0.60
𝑇𝑑𝑘 is the decrease key of the data structure used for queue. tdkはキューに使用されるデータ構造の縮小キーである。 0.80
𝑇𝑒𝑚 is the extract minimum of the data structure used. Temは、使用されるデータ構造の抽出最小値です。 0.80
III. Conclusion: Capacitated vehicle routing problem is an important topic that is always interpreted in the domain of optimizing, due to the wide range of use, this what make the eyes focused in this topic. III。 結論: キャパシタイトされた車両ルーティング問題は、幅広い用途のために最適化の領域において常に解釈される重要なトピックである。

0.74
In this paper I tired to implement an optimized solution that focused in the clustering part, one of the most important patterns in the routing algorithm, which is the responsible and the main effector when it comes to results, I tried to make this clustering benefits from the iterations to make it more mature. この論文では、ルーティングアルゴリズムにおいて最も重要なパターンであるクラスタリング部分に焦点を当てた最適化されたソリューションの実装にうんざりし、結果に関して責任と主要なエフェクタであるので、このクラスタリングのメリットをイテレーションから生かして、より成熟させたものにしようとしました。 0.72
Hence Capacitated vehicle routing problem CVRP is an NP-Hard classified problem, its hard to find the most optimal solution to solve it, all research and development tried to get near the optimal, but use cases play role. したがって、キャパシタブル車両ルーティング問題CVRPはNPハードクラシファイド問題であり、それを解決するために最も最適なソリューションを見つけることが困難であり、すべての研究開発は最適なものに近づこうとしましたが、ユースケースは重要な役割を果たします。

0.86
IV. References:  A Survey on the Vehicle Routing Problem and Its Variants, Intelligent Information Management, 2012, 4, 66-74 , http://dx.doi.org/10 .4236/iim.2012.43010 Published Online May 2012 (http://www.SciRP.or g/journal/iim) IV。 参考文献  A Survey on the Vehicle Routing Problem and its Variants, Intelligent Information Management, 2012 4, 66-74 , http://dx.doi.org/10 .4236/iim.2012.43010 Published Online May 2012 (http://www.SciRP.or g/journal/iim) 0.71
 Dijkstra's algorithm https://en.wikipedia .org/wiki/Dijkstra%2 7s_algorithm  Dijkstraのアルゴリズム https://en.wikipedia .org/Dijkstra%27s_al gorithm 0.60
 K-Means Clustering https://www.saedsaya d.com/clustering_kme ans.htm K-Means Clustering https://www.saedsaya d.com/clustering_kme ans.htm 0.50
 CoursMMM1 https://perso.univre nnes1.fr/isabelle.gr uais/CoursMMM1.pdf CoursMMM1 https://perso.univre nnes1.fr/isabelle.gr uais/CoursMMM1.pdf 0.40
A route flow that represents the best route to follow from a source through all nearest node and the depo, that will be like (Node 1, Node 3, Node 2, …, {0}) ソースから最も近いノードとデポを通る最良のルートを表すルートフロー(Node 1, Node 3, Node 2, ..., {0})。

0.77
 Méthode de Newton ,Michel Bierlaire, michel.bierlaire@epf l.ch, Laboratoire Transport et Mobilite´, EPFL - ENAC - TRANSP-OR Méthode de Newton, Michel Bierlaire, michel.bierlaire@epf l.ch, Laboratoire Transport et Mobilite ́, EPFL - ENAC - TRANSP-OR 0.92
pg. 5 https://transp-or.ep fl.ch/slides/Optimis ation/newton.pdf pg。 5 https://transp-or.ep fl.ch/slides/Optimis ation/newton.pdf 0.63
Hassan Moussa 2021 Hassan Moussa 2021 0.85
ページの最初に戻る