WEKO3
アイテム
多制約配送計画問題に対する集合被覆アプローチ
https://ipsj.ixsq.nii.ac.jp/records/31665
https://ipsj.ixsq.nii.ac.jp/records/31665a22ac73a-9f10-4994-a250-57cbfd47bb90
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL07113007.pdf (685.2 kB)
|
Copyright (c) 2007 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2007-07-03 | |||||||
| タイトル | ||||||||
| タイトル | 多制約配送計画問題に対する集合被覆アプローチ | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A set covering approach for a generalization of the pickup and delivery problem with time windows by allowing general constraints on each route | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 京都大学 | ||||||||
| 著者所属 | ||||||||
| キヤノンシステムソリユーシヨンズ | ||||||||
| 著者所属 | ||||||||
| 名古屋大学 | ||||||||
| 著者所属 | ||||||||
| 法政大学 | ||||||||
| 著者所属 | ||||||||
| 関西学院大学 | ||||||||
| 著者所属 | ||||||||
| MoldeCollege | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Canon System Solutions Inc. | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nagoya University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hosei University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kwansei Gakuin University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Molde College | ||||||||
| 著者名 |
橋本, 英樹
× 橋本, 英樹
|
|||||||
| 著者名(英) |
Hideki, Hashimoto
× Hideki, Hashimoto
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 各ルートに様々な制約を課すことを許した配送計画問題を考え、集合被覆アプローチに基づく近似解法を提案する。この問題は、すべての顧客を実行可能なルート集合で被覆するという集合被覆問題として定式化できる。本解法では、まず実行可能なルート集合を生成し、そのルート集合を修正するという操作を反復し、最後に、求めたルート集合に対応する集合被覆問題を解いて、本問題の解を得る。よい解を得るためには、ルート集合のサイズが大き過ぎずかつ十分な多様性を持つことが期待される。本解法では、ルート集合の修正にラグランジュ緩和の情報を利用することで、その実現を図る゜計算実験により、様々な制約を課した問題例に対して、本解法の効果を確認する。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We consider a generalization of the pickup and delivery problem with time windows by allowing general constraints on each route,and propose a heuristic algorithm based on the set covering approach,in which all requests are required to be covered by a set of feasible routes.Our algorithm first generates a set of feasible routes, and repeats reconstructing of the set by using information from a Lagrangian relaxation of the set covering problem corresponding to the set.The algorithm then solves the resulting set covering problem instance to find a good feasible solution for the original problem.We conduct computational experiments for instances with various constraints and confirm the flexibility and robustness of our algorithm. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2007, 号 66(2007-AL-113), p. 47-54, 発行日 2007-07-03 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
