https://www.jstage.jst.go.jp/article/jsaifpai/120/0/120_72/_pdf/-char/ja

2022/03/15

Masanori Shimokawa, Toshihiro Matsui

まとめ

貪欲に次の集荷地点を決定

Abstract

既存研究：1体のエージェントは一度に1つのタスクを実行

本研究：エージェントが積載容量の制限内で複数のタスクを同時に実行

1　はじめに

あるタスクの集荷位置から配達位置へ向かう経路の途中に、他のタスクの集荷位置と配達位置を含むことができる問題へ拡張

目的：makespanを最小化

二つの基礎的な解法を提案

• 解法１：予め、全てのタスクの集荷位置と配達位置を、エージェント順に貪欲的に割り当ててか ら、集配タスクを実行
• 解法２：各エージェントに目的地となるタスクの集荷位置または配達位置を割り当て、その位置に向かって移動し、目的地にたどり着いたエージェントから順に、次の目的地となるタスクの集荷位置または配達位置を割り当てる

実験により二つの提案手法を評価

• 結果１：タスクの実行時間を考慮する解法2の方がmakespanを削減
• 結果２：タスク数が増えるにつれて、解法2の効果が大きい

初期経路に含まれる複数タスクの割り当て問題をTSPとして定式化

2　背景