本研究では，複数の配送先に対する貨物配送のための二酸化炭素排出量最少経路探索アルゴリズムを考案することで，低炭素社会の実現への一助をなすことを目的としている．
二酸化炭素排出量削減の必要性
2005年2月に発効した京都議定書は，2008年から2012年までの「第一約束期間」内に，二酸化炭素に代表される温室効果ガスの合計排出量を1990 年比で6%削減するという目標を日本に対して定めている．一方，民主党は「2020年までに1990年比で25％削減」という中期目標を掲げており，両目標を達成するためには二酸化炭素排出量削減への対策が必要不可欠である．また，2009年4月1日に施行された改正省エネ法では，物流事業者と荷主に二酸化炭素削減活動計画と成果報告が義務付けられており，物流事業者にとって貨物配送にかかる二酸化炭素排出量の削減は大きな課題となっている．長距離輸送や大量輸送では，二酸化炭素排出量が比較的少ない鉄道や船舶へのモーダルシフトが有用な手段であるが，近距離範囲内で小規模の貨物を配送する場合には，貨物自動車による輸送が欠かせない．特に最近は，インターネットショッピングの爆発的な普及によって個人宅向け配送の需要が高まっており，貨物自動車での配送によって排出された二酸化炭素の削減は急務であるといえる．
二酸化炭素排出量最少経路探索問題
低コストで手軽に取り組める二酸化炭素排出量削減対策として，最短経路での配送が考えられる．しかし，1回の配送作業で複数の配送先に重量の異なる貨物を配送する場合には，配送順により各区間の積載重量が変化するため，最短経路が二酸化炭素排出量を最少にする経路になるとは限らない．そこで，最短経路探索とは別の探索アルゴリズムの考案が必要となる．経路探索問題の代表例として巡回セールスマン問題がよく知られているが，巡回する地点(ノード)間距離が与えられているにもかかわらず，ノードが増加すると組合せ爆発が発生するNP完全問題であり，解を得るのに多大な時間を要する．本研究で対象にする問題も同様の課題を抱えている．着荷主が不在で貨物を配送センターに持ち帰ることになったり，配送途中で再配達を依頼されたりした場合には，配送順の再検討が必要になるため，探索アルゴリズムの計算時間は許容範囲内におさまることが必須条件である．また，物流事業者が保有するトラックの台数や種類が限られている場合など，多様な配送状況に対応可能であることが求められる．
二酸化炭素排出量最少経路探索では，最短経路探索よりも，解の評価値が配送順に大きく依存する．例えば，連続する2地点の順序が入れ替わった場合，最短経路探索では，前後の距離は変わっても当該2地点間の距離は変わらない．しかし，二酸化炭素排出量最少経路探索では，前後の二酸化炭素排出量に加え，当該2 地点間で排出される二酸化炭素の量も変化する．また，同じ部分経路でも，全経路における位置によって二酸化炭素排出量は異なる．二酸化炭素排出量が少なくなるような近隣地点の訪問順を探索すると同時に，総排出量が少なくなるような近隣地点の集まりの並べ方を探索するという並行探索が必要である．これらを勘案して「共生進化」の考え方を適用することとする．
共生進化の適用
共生進化とは，最適解探索アルゴリズムとして広く知られている遺伝的アルゴリズム（Genetic Algorithm, GA）のモデルの1つである．野球やサッカーなどのチームで戦うスポーツでは，各選手の力量だけでなく，チームの構成や選手の配置も勝負を大きく左右するため，個人の力量を高めつつ，最適な人員配置を模索しなければならない．これをモチーフとした進化計算アルゴリズムが共生進化である．部分解を個体とする集団と，部分解の組合せを個体とする全体解集団を保持し，両集団を並行して進化させる．1集団を進化させる単純GAよりも集団内の多様性が維持され，局所解への収束を回避しつつ，効率よく最適解を見つけることができる．研究代表者により，帰納論理プログラミング，決定木生成，近赤外スペクトルを用いたポリマー判別，雑音重畳画像の強調，プロモータモデリングのための隠れマルコフモデル生成，個人の感性に合わせた自動作曲，土地利用マイクロシミュレーションにおける観測データと推定データの適合度評価など，数多くの分野における共生進化の適用手法が提案され，有用であることが実証されている．部分解と，部分解の組合せを同時に学習できる点で，共生進化は二酸化炭素排出量最少経路探索に適しているといえる．
以上の背景を踏まえ，本研究の前段階として，共生進化に基づいて二酸化炭素排出量最少経路を探索するシステムを試作し，最短経路よりも二酸化炭素排出量が10%程度少ない経路を見つけることに成功している．