廃棄物収集運搬のための車両ルーティングの最適化

Optimization of Vehicle Routing for Waste Collection and Transportation.

• Hailin Wu
• Fengming Tao
• Bo Yang

抄録

本論文では、中国における都市ごみ収集輸送の最適化問題を解決するために、廃棄物管理システムにおける優先度考慮グリーンビークルルーティング問題(PCGVRP)モデルを構築し、このモデルを解決するために特定のアルゴリズムを設計した。特に、病院廃棄物や医療廃棄物を含む優先度の高い廃棄物箱の場合、有害な廃棄物はすぐに回収する必要があるため、即時回収サービスの可能性に注目しています。そうしないと、危険または悪影響を及ぼす可能性がある。環境保護の観点から、提案するPCGVRPモデルでは、温室効果ガス（GHG）排出コストと従来の廃棄物管理コストの両方を考慮しています。廃棄物の充填レベル（WFL）を考慮し、廃棄物容器にセンサーを設置することで、固定ルートではなく動的ルートを実現し、廃棄物収集運搬の経済性と効率性を向上させることができます。最適解は局所探索ハイブリッドアルゴリズム(LSHA)によって得られる。すなわち、初期最適解を粒子群最適化(PSO)によって得た後、初期最適解に対して局所探索を行い、大域探索機能を利用した模擬アニーリング(SA)アルゴリズムによって最適化する。提案するLSHAアルゴリズムの有効性を検証するために、容量性車両ルーティング問題(CVRP)のデータベースからいくつかのインスタンスを選択する。また、信頼性の高い結果と結論を得るために、廃棄物収集運搬に関するデータを用いた事例を用いてPCGVRPモデルの検証を行い、優先度の高いビン数とWFLの一連の値を設定してモデルの有効性と実用性を検証した。その結果、(1)提案モデルは従来モデルと比較して42.3%のマイナス効果の低減を達成できること、(2)WFLを60%から80%の間の一定の値に設定することで高い収集運搬効率を実現できること、(3)WFLの具体的な値は優先度の高いゴミ箱の数によって決定されることが示された。最後に、これらの結論に基づいて、環境保護行政や廃棄物管理機関に対して建設的な提案を行った。

For the sake of solving the optimization problem of urban waste collection and transportation in China, a priority considered green vehicle routing problem (PCGVRP) model in a waste management system is constructed in this paper, and specific algorithms are designed to solve the model. We pay particular concern to the possibility of immediate waste collection services for high-priority waste bins, e.g., those containing hospital or medical waste, because the harmful waste needs to be collected immediately. Otherwise, these may cause dangerous or negative effects. From the perspective of environmental protection, the proposed PCGVRP model considers both greenhouse gas (GHG) emission costs and conventional waste management costs. Waste filling level (WFL) is considered with the deployment of sensors on waste bins to realize dynamic routes instead of fixed routes, so that the economy and efficiency of waste collection and transportation can be improved. The optimal solution is obtained by a local search hybrid algorithm (LSHA), that is, the initial optimal solution is obtained by particle swarm optimization (PSO) and then a local search is performed on the initial optimal solution, which will be optimized by a simulated annealing (SA) algorithm by virtue of the global search capability. Several instances are selected from the database of capacitated vehicle routing problem (CVRP) so as to test and verify the effectiveness of the proposed LSHA algorithm. In addition, to obtain credible results and conclusions, a case using data about waste collection and transportation is employed to verify the PCGVRP model, and the effectiveness and practicability of the model was tested by setting a series of values of bins' number with high priority and WFLs. The results show that (1) the proposed model can achieve a 42.3% reduction of negative effect compared with the traditional one; (2) a certain value of WFL between 60% and 80% can realize high efficiency of the waste collection and transportation; and (3) the best specific value of WFL is determined by the number of waste bins with high priority. Finally, some constructive propositions are put forward for the Environmental Protection Administration and waste management institutions based on these conclusions.