電動車両の最適ルートを高速計算する新アルゴリズム
物流業界は今、その根幹を揺るがす変革の真っ只中に立っている。環境規制の強化と企業のESG（環境・社会・ガバナンス）への関心の高まりを背景に、世界中の配送企業が従来のディーゼル車から電動車両（EV）への大規模な転換を進めている。しかし、この移行は単なる動力源の置き換えにとどまらない。電動車両特有の「航続可能距離」と「充電インフラへの依存」という二つの制約が、従来の物流ルート最適化の常識を根底から覆している。この複雑な課題、電動車両路線計画問題（EVRP: Electric Vehicle Routing Problem）の解決に、中国・安徽大学の研究チームが画期的なアプローチを提案した。
この新アルゴリズムは、単に計算速度を上げるだけでなく、最適解に至るまでの「プロセス」そのものを革新している。従来のアプローチでは、航続距離、積載量、充電ステーションの位置、交通状況など、無数の変数を同時に考慮しながら最短ルートを探索する必要があり、計算量が膨大になり、大規模な配送網では現実的な時間内に最適解を見つけることが極めて困難だった。特に、EVのバッテリー残量がルートの途中で尽きてしまう「走行不能リスク」を回避するためには、過剰な安全マージンを設ける必要があり、結果として効率の悪いルート計画を余儀なくされてきた。
安徽大学人工知能学院の王朝（Wang Chao）准教授らの研究チームは、この難題を「分割して征服する」戦略で解決した。彼らが開発した「二重集団協同進化アルゴリズム」（COEA: Dual-population Co-Evolutionary Algorithm）の核心は、複雑なEVRPという「本物の問題」と、その一部を無視した「簡単な問題」の二つの集団を並行して進化させ、互いに有益な情報を交換させるという発想にある。
まず、「簡単な問題」として、電動車両の最大の制約である「電力制約」を一時的に無視した「容量制約付き車両路線計画問題」（CVRP: Capacitated Vehicle Routing Problem）を設定する。このCVRPは、従来のガソリン車の配送問題に近いもので、各車両の積載量と顧客の需要量のバランスを取ることに集中できる。そのため、計算がはるかに簡単で、アルゴリズムは非常に高速に「距離的に最短かつ効率的なルートの骨格」を発見することができる。この集団は、まるで「設計図を作成する建築家」のようだ。
一方、「本物の問題」であるEVRPの集団は、この設計図を受け取って、その上に「電力制約」という現実の壁を構築しなければならない。しかし、ここで重要なのは、CVRPの「設計図」とEVRPの「現実の建物」は構造が異なるため、情報をそのままコピーできない点だ。CVRPの最短ルートが、EVの航続距離では到底カバーできない可能性がある。この「言語の違い」を解消するために、研究チームは人工知能の力を借りた。
彼らが用いたのは「ノイズ除去オートエンコーダ」（DAE: Denoising Autoencoder）と呼ばれる機械学習モデルである。DAEは、ある種の「翻訳機」の役割を果たす。まず、CVRP集団が見つけた優れたルート（エリート解）を、特別な「距離隣接行列」という数学的表現に変換する。この行列は、単なる地理的な距離だけでなく、どの顧客が同じ車両に割り当てられているかという「車両アサイン情報」まで含んだ、非常に豊かな情報を持つ。この行列をDAEに入力すると、DAEは学習した知識に基づいて、それをEVRPの世界で意味のある形に「翻訳」する。つまり、CVRPの効率的なルート設計を、EVRPの電力制約下で実現可能な形に変換するのだ。
この翻訳された「設計図」は、EVRP集団の新しい「子孫」として挿入され、進化のプロセスに組み込まれる。これにより、EVRP集団は、自力でゼロから最適ルートを探すよりもはるかに短い時間で、効率的なルートの候補を手に入れることができる。さらに、このプロセスは双方向的である。EVRP集団が見つけた、充電ステーションを巧みに利用した優れたルートも、逆にDAEで翻訳され、CVRP集団にフィードバックされる。これにより、CVRP集団は「電力制約がある世界では、このようなルートの構造が有利だ」という情報を学習し、次第にEVに最適化された「設計図」を描くようになる。
この二つの集団が互いに情報を交換し、助け合う「協同進化」のプロセスこそが、COEAの真の強みである。まるで二人の専門家が協力してプロジェクトを進めるように、一方が「効率性」に特化し、他方が「現実性」に特化することで、全体としての成果が飛躍的に向上する。研究チームは、このアルゴリズムを、200人および400人の顧客を対象とした大規模な標準テストデータセットで検証した。その結果、従来の最先端のアルゴリズムと比較して、18のテストケースのうち11件で最短距離を達成した。特に大規模な400顧客のケースでは、その優位性が顕著に現れた。これは、都市部のような複雑な環境での実用性を強く示唆している。
さらに重要なのは、その「収束速度」の速さである。アルゴリズムが最適解に近づく様子をグラフで表すと、COEAは他のアルゴリズムに比べて非常に急峻な曲線を描き、極めて短い時間で高性能な解に到達している。これは、実際の物流現場において極めて重要だ。天候の急変、交通渋滞、あるいは直前での注文変更など、リアルタイムでルートを再計算する必要がある場面では、計算時間が命取りになる。COEAのような高速なアルゴリズムがあれば、配送センターはより柔軟かつ迅速に意思決定を行い、配達遅延を最小限に抑えることができる。
この研究の意義は、単に「速いアルゴリズムができた」ということ以上にある。それは、AIと最適化技術の融合の新たな形を示している点にある。DAEは、単に計算を行う道具ではなく、二つの異なる問題の「知識」を橋渡しする「知性」を持っている。この「知識移転」（Knowledge Transfer）の概念は、今後のAI研究に大きな影響を与えるだろう。複雑な問題を解くためには、必ずしもその問題に特化した巨大なAIモデルをゼロから学習させる必要はなく、関連する「簡単な問題」の知識を上手に活用すれば、より効率的に学習できることを示している。
物流企業にとって、この技術は即座に実用化可能な価値を提供する。例えば、大手宅配便業者は、毎日何千台ものEVを投入して配達を行っている。現在のルート計画ソフトウェアが、COEAのような技術を採用すれば、以下のような具体的なメリットが得られる。 第一に、総走行距離の削減である。最短ルートが見つかれば、それだけ燃料（電力）の消費量が減り、CO2排出量の削減に直結する。これは、企業のESG報告書において非常に重要な指標となる。 第二に、車両稼働率の向上である。走行不能リスクが低減されれば、無駄な予備車両の手配や、配達員の待機時間が減る。また、充電タイミングが最適化されれば、充電に費やす時間が短縮され、その分だけ走行時間が増える。 第三に、顧客満足度の向上である。ルートが安定し、予測可能な精度が高まれば、配達時間帯の指定がより正確に行えるようになる。これは、オンラインショッピングの普及が進む現代において、競争力の源泉となる。
研究チームは、このアルゴリズムのさらなる発展にも言及している。例えば、バッテリーの劣化や、季節・気温による航続距離の変動、あるいは複数の充電方式（急速充電、スワップステーションなど）に対応するように拡張できる可能性がある。また、都市のデジタルツイン（Digital Twin）と連携させれば、リアルタイムの交通情報や天候データを反映した、より高精度な動的ルート最適化が可能になる。
安徽大学の王朝准教授は、「我々のアプローチは、複雑な問題に立ち向かうための新しいパラダイムを提供します。電動車両の普及は、持続可能な社会の実現に不可欠です。しかし、その真のポテンシャルを引き出すためには、それに見合った知的なインフラが必要です。このアルゴリズムは、その一歩を踏み出したにすぎません」と語っている。
結論として、この二重集団協同進化アルゴリズムは、電動物流の課題解決に向けた強力なツールである。それは、単なる計算技術の進歩ではなく、AIが人間の知恵と協調し、複雑な現実世界の問題を解くための「共進化」の可能性を示している。今後、都市の空を走る無数の電動配送車両の背後で、このような高度なアルゴリズムが静かに働き、より効率的で、よりクリーンな物流の未来を支えていくだろう。
電動車両の最適ルートを高速計算する新アルゴリズム 王朝，秦芳，劉蓉蓉，江浩，安徽大学人工知能学院 CAAI Transactions on Intelligent Systems, DOI: 10.11992/tis.202209007