配車問題 最大積載量が異なるトラックをそれぞれ何台ず つか持っている配送センターから、 ｎ個の配送先へ荷物を配送する場合、 総距離を最小にするためには、どのような路線 をとったらよいか。 巡回問題の一種 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 考え方 配送先ａ 配送先ｂ β α センター γ 配送先ａ α β センター （１図） （１図）の場合の距離 ： ２α＋２β （２図）の場合の距離 ： α＋β＋γ （１図）と（２図）の差 2015/10/1 配送先ｂ ： α＋β－γ ＝ Ｓａｂ Ｓａｂの値だけ輸送距離が増減する。 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ （２図） 考え方 配送先ａ 配送先ｂ α β α センター （１図：往復配送） γ 配送先ａ α＋β－γ＝Ｓａｂ 配送先ｂ β センター （２図：巡回配送） Ｓａｂ間の値だけ輸送距離が増減する。 すなわち Ｓａｂ ＞ ０ ならば 減 （巡回配送にする） Ｓａｂ ＝ ０ ならば 不変 Ｓａｂ ＜ ０ ならば 増 （往復配送にする） 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 考え方 配送先ａ 配送先ｂ 配送先ａ センター 配送先ｂ α β α γ （１図） β センター （２図） 配送先ａから配送先ｂへ行くのに、 節約できる距離を ＳＥＴＵＹＡ（ａ，ｂ）とすると、 配送先ａから配送先ｂへ行くときの距離の節約分は、 ＳＥＴＵＹＡ（ａ，ｂ）＝ （センターとａの距離）＋（センターとｂの距離）－（ａとｂの距離） 2015/10/1 ＝ α ©ＡＴＳＵＴＯ＋ＮＩＳＨＩＯ β － γ 問題（例11・1） － 配送先 表１：配送先 配送先 センターからの距離 １ ２ ３ ４ ５ ６ 13 8 16 12 12 12 需要量 100 150 200 130 250 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ７ 14 ８ 15 90 120 290 問題（例11・1） － 配送先相互間の距離 表２ ： 配送先相互間の距離（γ） １ ２ ３ ４ ５ ６ ７ ８ １ ０ ２ ７ ０ ３ １１ １０ ０ ４ ２５ ２０ １５ ０ ５ ２７ ２０ ２８ １１ ０ ６ ２５ ２０ ２８ ２４ ２５ ０ ７ ２７ ２３ ３０ ２８ ２７ ７ ０ 2015/10/1８ １８ １４ ２１ ２０ １７ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ１７ １１ ０ 問題（例11・1） － トラックの制限 表３ ： 利用可能トラックの制限 ３００ｋｇ積 － 10,000 台 ４００ｋｇ積 － 3台 ５００ｋｇ積 － 1台 これらの条件のもとで、 総配送距離の最も短くて済む配車計画を考える 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 考え方 ＳＥＴＵＹＡ（ａ，ｂ）＝ （センターとａの距離）＋（センターとｂの距離）－（ａとｂの距離） この式から節約表を作成する。 （負の値は節約不可能 ⇒ 往復配送のまま） １ ２ ３ ４ ５ ６ ７ ８ 16+12－15 １ ０ ２ １４ ０ ３ １８ １４ ０ ４ ０ ０ １３ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ １９ 2015/10/1８ ０ －１ ０ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ ０ ８ ０ 手順ⅰ センターから全ての配送先に１台ずつの トラックで配送するときの総距離は、 2×（13＋8＋16＋12＋12＋12＋14＋5） ＝184 で、 必要なトラックの台数は、 300kg積－8台。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅰ（ルート） （１５０） （１００） 300 ２ ６ １ １３ （２００） （９０） 300 ８ １２ １６ ３ 300 １４ Ｃ ７ 300 （１２０） 300 １２ ５ １２ 300 ４ （１３０） 2015/10/1 300 ５ 300 （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅰ→手順ⅱ ＳＥＴＵＹＡ（ａ，ｂ）＝ （センターとａの距離）＋（センターとｂの距離）－（ａとｂの距離） 正の値のルートは節約可能（巡回配送にする）。負の値のルートはそのまま。 １ ２ ３ ４ ５ ６ ７ １ ０ ２ １４ ０ ３ １８ １４ ０ ４ ０ ０ １３ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ １９ 2015/10/1８ ０ －１ ０ ８ 節約高最大 ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ ０ ８ ０ 手順ⅱ 節約高の最大のものを節約表から探すと、 ＳＥＴＵＹＡ（6,7）＝19 したがって、 Ｃ－６－７－Ｃ を１台のトラックで配送することにすると、 ６の需要：90、７の需要：120で、 合計210kgとなるので、 300kg積のトラックを使用する。 これ以外の配送先は、１台ずつのトラックで配送することにすると、 総配送距離は､184－19＝165kmとなり、 トラックの台数は300kg積７台となる。 ＳＥＴＵＹＡ（6,7）は調べたので、ＳＥＴＵＹＡ（6,7）＝0 とする。 これ以上節約できない 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅱ（ルート） （１５０） （１００） （９０） ２ ６ １ １３ ８ １２ （７） ３００ （２００） １６ ３ １４ Ｃ １２ １２ ７ （１２０） ５ ４ （１３０） 2015/10/1 ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅱ（節約表） 総配送距離 ： １８４－１９＝１６５ 使用トラック ： 300kg－７台 （残り500－１台 400－３台） １ ２ ３ ４ ５ ６ ７ ８ １ ０ ２ １４ ０ ３ １８ １４ ０ ４ ０ ０ １３ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ８ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅲ 同様に、節約表より、その次に節約高最大のものを探すと、 ＳＥＴＵＹＡ（1,3）＝18 したがって、Ｃ－１－３－Ｃを１台のトラックで配送せればよい。 １の需要：100、３の需要：200で、 合計300kgとなるので、 300kg積のトラックを使用する。 総配送距離は､165－18＝147kmとなり、 トラックの台数は300kg積６台に減る。 ＳＥＴＵＹＡ（1,3）は調べたので、ＳＥＴＵＹＡ（1,3）＝0 とする。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅲ（ルート） （１５０） （１００） （９０） ２ ６ １ （１１） （２００） １３ ８ ３００ （７） ３００ １６ ３ １２ （１２０） １４ Ｃ １２ １２ ７ ５ ４ （１３０） 2015/10/1 ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅲ（節約表） 総配送距離 ： １６５－１８＝１４７ 使用トラック ： 300kg－６台 （残り500－１台 400－３台） １ ２ ３ ４ ５ ６ ７ ８ １ ０ ２ １４ ０ ３ ０ １４ ０ ４ ０ ０ １３ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ８ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅳ 同様に、節約表より、その次に節約高最大のものを探すと、 ＳＥＴＵＹＡ（1,2）＝14 （同じ値が２つ以上あるときは、出発地番号が早いほう） Ｃ－１－３－Ｃが決定されているので、それとドッキングさせ、 Ｃ－３－１－２－Ｃ を１台のトラックで配送すればよい。 １の需要：100、２の需要：150、３の需要：200で、 合計450kgと なるので、500kg積のトラックを使用する。 総配送距離は､147－14＝133kmとなり、 トラックの台数は500kg積１台、300kg積４台となる。 ＳＥＴＵＹＡ（1,2）は調べたので、ＳＥＴＵＹＡ（1,2）＝０ とする。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅳ（ルート） （１５０） （１００） （９０） ２ ６ １ （１１） （２００） １３ ８ ５００ （７） ３００ １６ ３ １２ （１２０） １４ Ｃ １２ １２ ７ ５ ４ （１３０） 2015/10/1 ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅳ（節約表） 総配送距離 ： １４７－１４＝１３３ 使用トラック ： 300kg－４台 500kg－１台 １ ２ ３ ４ ５ （残り500－０台 400－３台） ６ ７ ８ １ ０ ２ ０ ０ ３ ０ １４ ０ ４ ０ ０ １３ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ８ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅴ ＳＥＴＵＹＡ（2,3）＝14が最大であるが、このルートは既 に決定済なので、ＳＥＴＵＹＡ（2,3）＝0 とする。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅴ（節約表） 総配送距離 ： １４７－１４＝１３３ 使用トラック ： 300kg－４台 500kg－１台 １ ２ ３ ４ ５ （残り500－０台 400－３台） ６ ７ ８ １ ０ ２ ０ ０ ３ ０ ０ ０ ４ ０ ０ １３ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ８ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅵ 残ったものについて、 ＳＥＴＵＹＡ（3,4）＝13 が最大である。 ３は前に決定した Ｃ－３－１－２－Ｃ に組み込まれているので、 それにリンクさせ、Ｃ－４－３－１－２－Ｃ を１台のトラックで 配送することを考えると、 ４の需要：130、３の需要：200、１の需要：100、２の需要：150 の 合計580kgとなり、使用可能なトラックはない。 したがって、 このルートは採用不可能だから、ＳＥＴＵＹＡ（3,4）＝0 とする。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅵ（ルート） （１５０） （１００） （９０） ２ ６ １ ５００ （１１） ８ １２ （７） ３００ （２００） １６ ３ Ｃ × （１２０） １４ １２ １２ ７ ５ ４ （１３０） 2015/10/1 ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅵ（節約表） 総配送距離 ： １４７－１４＝１３３ 使用トラック ： 300kg－４台 500kg－１台 １ ２ ３ ４ ５ （残り500－０台 400－３台） ６ ７ ８ １ ０ ２ ０ ０ ３ ０ ０ ０ ４ ０ ０ ０ ０ ５ －２ ０ ０ １３ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ８ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅶ 残ったものについて、 ＳＥＴＵＹＡ（4,5）＝13 が最大である。 Ｃ－４－５－Ｃ を400kg積で配送する。 その結果、 総配送距離は、133－13＝120km となる。 ＳＥＴＵＹＡ（4,5）＝0 とする。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅶ（ルート） （１５０） （１００） （７） （９０） ２ ６ １ （１１） （２００） ５００ ８ １２ １２ （１３０） 2015/10/1 （１２０） １４ Ｃ ４ （７） ３００ １６ ３ １２ ７ ５ ４００ （１１） ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅶ（節約表） 総配送距離 ： １３３－１３＝１２０ 使用トラック ： 300kg－２台 400kg－１台 500kg－１台（残り500－０、400－２台） １ ２ ３ ４ ５ ６ ７ ８ １ ０ ２ ０ ０ ３ ０ ０ ０ ４ ０ ０ ０ ０ ５ －２ ０ ０ ０ ０ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ８ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅷ 残ったものについて、 ＳＥＴＵＹＡ（7,8）＝8 が最大である。 Ｃ－８－７－６－Ｃ を500kg積で配送すればよいが、 500kg積トラックは１台で、既に手順ⅳで使用している ので、このルートは採用不可能。 したがって、ＳＥＴＵＹＡ（7,8）＝0 とする。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅷ（ルート） （１５０） （１００） （７） （９０） ２ ６ １ （１１） （２００） ８ ５００ （７） ３００ １６ ３ １２ （１２０） １４ Ｃ ７ × １２ １２ ４ （１３０） 2015/10/1 ５ ４００ （１１） ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 手順ⅷ（節約表） 総配送距離 ： １３３－１３＝１２０ 使用トラック ： 300kg－２台 400kg－１台 500kg－１台（残り500－０台 400－２台） １ ２ ３ ４ ５ ６ ７ ８ １ ０ ２ ０ ０ ３ ０ ０ ０ ４ ０ ０ ０ ０ ５ －２ ０ ０ ０ ０ ６ ０ ０ ０ ０ －１ ０ ７ ０ －１ ０ －２ －１ ０ ０ 2015/10/1８ ０ －１ ０ ０ ０ －３ ０ ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ０ 手順ⅸ 残ったものについて、節約表をみると、正の値がない。 これで、手順終了。 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ 手順ⅸ（ルート） （１５０） （１００） （７） （９０） ２ ６ １ （１１） （２００） ８ ５００ １２ １２ （１３０） 2015/10/1 （１２０） １４ Ｃ ４ （７） ３００ １６ ３ １２ ５ ７ ３００ ４００ （１１） ５ （２５０） ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ ８ （２９０） 結果の検討 ◎ ８カ所のセンター全てに往復配送する場合。 総配送距離：184km 使用トラック：300kg積－８台 ◎ 最短経路の場合。 総配送距離：120km 使用トラック：500kg積－１台 400kg積－１台 300kg積－２台 2015/10/1 ©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
© Copyright 2024 ExpyDoc
