凸型時間ペナルティ関数付き配送計一画問題·スケジューリング問題に対する反復局所探索法

摘要

配送計画問題とは、様々な制約条件の下で，複数の斬両を円いて全ての客をちょうど1回ずつ訪問するような経路の中で，コスト鼓小のものを求める問題である．この問題はNP国経であるため，現実的な方法ヒして種々の近似解法が提案されている．通常の定式化では，制約条件として，客が指定する時間枠内にサービスを開始しなければならないという時間枠制約と，客の要求量の総和が車両の容量を超えてはいけないという容量別約が課せられる．本研究では，これらの制約を一般化している．まず，時間枠制約については，凸型ペナルティ関数を用いて緩和し，考慮制約として扱う．容量制約に対しては，客への荷物の配達（配荷）に加えて，客からの荷物の返却（集荷）も考える．