概要：

In the vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the vehicle capacity and where each customer is visited once. In the split delivery vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. Moreover, the demand of each customer can be greater than the capacity of the vehicles. The SDVRP is NP-hard, even under restricted conditions on the costs, when all vehicles have a capacity greater than two, while it is solvable in polynomial time when the vehicles have a maximum capacity of two.

We show that the cost savings that can be reached by allowing split deliveries is at most 50%. The variant of the VRP in which the demand of a customer may be larger than the vehicle capacity, but where each customer has to be visited a minimum number of times, is also considered. We show that the cost savings that can be reached by allowing more than the minimum number of required visits is again at most 50%. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the vehicle capacity. Computational results are also shown to estimate the average savings that can be obtained with split deliveries.

A simple and effective tabu search algorithm is compared with a sophisticated heuristic that, starting from the solution obtained by the tabu search algorithm and using the information collected during the tabu search, builds promising routes and solves MILP models to decide which routes to use and how to serve the customers through those routes. Computational experiments are reported for a set of benchmark problems.

概要：

ロジスティクスの理論と実務には，未だ大きなギャップがある．これを埋めるため に，私たち研究者側からできるとこは，旧来の理論的な研究対象であった古典モデル を実務に直結するように拡張すること，拡張されたモデルに対してアルゴリズムを導 き出すこと，さらは，これらのアルゴリズムを組み込んだ意思決定支援システムを構 築することである。本稿では，筆者らが開発してきたロジスティクス最適化のための 意思決定支援システムである在庫方策最適化，安全在庫配置，配送計画，ロジスティ クス・ネットワーク設計，ロットサイズ決定，スケジューリング，収益管理につい て，その理論的背景を解説するとともに，幾つかの事例を紹介する．

概要：

全国規模の物流サービスを実現する輸送ネットワークの設計問題を取り 上げる。この問題では、全国に配置された拠点に荷物を集約し、目的拠 点の異なる荷物を混載することで輸送効率を高める物流形態を扱う。す べての出発拠点と目的拠点のペアごとに最大到達時間が規定されてお り、その時間制約の範囲で荷物の輸送経路とキャリアの運行スケジュー ルを決定する。この問題に対し、荷物のルーティングと キャリア割当の の二つの問題に分割するアプローチを提案し、その有効性を議論する。