遺伝的アルゴリズムを用いた外航定期船航路編成生成システムの研究開発

基于遗传算法的远洋班轮航线形成生成系统的研究与开发

基本信息

批准号：
17760652
负责人：
小林充
金额：
$ 1.47万
依托单位：
National Maritime Research Institute
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17760652/
关键词：
遺伝的アルゴリズム最適化外航定期船海上輸送

项目摘要

前年度に明らかになった試作システムの有する問題点について、改善を行うこととし、次のような作業を行うことで新たな最適化システムを作成した。・貨物の経路配分算出手法に、多項ロジットモデルを取り入れ、PIERS米国税関データベースからの貨物量カウントをもとに最尤法によってパラメータ決定をした。これにより、資料の収集の難しい航路ごとの特徴(運賃や営業力、営業方針等)や、貨物到着までの所要日数と集荷力の関係を数値化した。また、どの経路にも割り当てられない貨物が極力少なくなるように割当を行った。これによって、貨物量の経路配分結果が現状の貨物流動に近いものとなった。・従来システムが寄港曜日を基とした染色体表現であり、変異や交叉に対する耐性がなく致死個体の発生確率が高いことが問題だった。このため新システムでは航行速度を基本情報とした表現に変更した。その結果、最適化の速度が2倍以上に高速化した。染色体の評価値の平均が従来システムに比べ非常に高いことが確認でき、変異に対する耐性が高いため変異を受けた個体が死滅せずに進化する機会が与えられるようになったことが速度向上に寄与していると考えられる。・従来システムでは所要時間の見積が詳細でなかったため、寄港数がむやみに多くなる問題があった。新システムでは荷役時間、スケジュールの乱れの回復のための余裕時間等スケジュール評価を詳細にしたことにより、寄港数が増加せず、かつ時間的余裕を保ちながら収益を実在航路に比べ11%増加させることができた。結果として、収益力があり、運航に無理のない航路案を短時間に作成するシステムを構築する目標が達成された。一方、航路数が実在航路9に対し編成航路案が7航路であった。少ない航路で十分に競争力のある編成を作成できるともいえるが、航路数の増加方向に対する淘汰圧が減少方向に比べ強いと考えられ、これを解決するアルゴリズム開発が課題として残された。

我们决定改进前一年暴露的原型系统的问题，并通过执行以下任务创建新的优化系统。 - 采用多项logit模型作为计算货物航线分配的方法，并根据PIERS美国海关数据库的货物量计数使用最大似然法确定参数。由此，我们量化了每条航线的数据采集困难的特征（如运价、销售队伍、销售政策等），以及货物到达所需天数与收集能力之间的关系。此外，进行分配是为了尽量减少无法分配到任何航线的货物量。结果，货量的航线分配结果变得接近当前的货流量。 - 传统系统的问题是，染色体表达是根据停靠港当天进行的，对突变或交叉没有抵抗力，导致个体死亡的概率很高。为此，新系统改为使用导航速度作为基本信息。结果，优化速度提高了一倍以上。经证实，染色体的平均评估值远高于传统系统，并且由于该系统对突变具有很强的抵抗力，因此发生突变的个体现在有机会在不死亡的情况下进化，从而提高了速度。认为这有贡献。 - 在传统系统中，所估计的所需时间并不详细，因此存在港口停靠次数不必要地大量的问题。新系统提供了详细的时间表评估，例如货物装卸时间和从时间表中断中恢复的裕度时间，从而与现有航线相比，在不增加港口停靠数量的情况下，收入增加了 11%，同时保持了时间裕度。。从而达到了构建一个能够在短时间内创建可盈利且合理运营的航线计划的系统的目标。另一方面，航线数量为 9 条，而计划航线为 7 条。虽然可以说用少量的路线可以创建一个足够有竞争力的组织，但人们认为增加路线数量方向的选择压力比减少路线数量方向的选择压力更大，并且开发一种算法来解决这个问题仍然是一个挑战。