JP5772332B2 - 巡回路決定についてのプログラム、方法及び装置 - Google Patents

巡回路決定についてのプログラム、方法及び装置 Download PDF

Info

Publication number
JP5772332B2
JP5772332B2 JP2011158552A JP2011158552A JP5772332B2 JP 5772332 B2 JP5772332 B2 JP 5772332B2 JP 2011158552 A JP2011158552 A JP 2011158552A JP 2011158552 A JP2011158552 A JP 2011158552A JP 5772332 B2 JP5772332 B2 JP 5772332B2
Authority
JP
Japan
Prior art keywords
work
storage unit
stored
execution order
evaluation value
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2011158552A
Other languages
English (en)
Other versions
JP2013025509A (ja
Inventor
秀直 岩根
秀直 岩根
知文 吉良
知文 吉良
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2011158552A priority Critical patent/JP5772332B2/ja
Priority to US13/527,824 priority patent/US20130024227A1/en
Publication of JP2013025509A publication Critical patent/JP2013025509A/ja
Application granted granted Critical
Publication of JP5772332B2 publication Critical patent/JP5772332B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem

Landscapes

  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Marketing (AREA)
  • Game Theory and Decision Science (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Development Economics (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Tourism & Hospitality (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • General Factory Administration (AREA)

Description

本技術は、制約条件付きの巡回路決定技術に関する。
巡回セールスマン問題（Traveling Salesman Problem）は、例えばｎ個の都市（作業地点又は作業場所とも呼ぶ）と各都市間の距離を入力として、各都市を１度ずつ訪問して元に戻る巡回路の中で総移動距離が最小のものを得る問題である。この問題はＮＰ困難問題として知られており、組み合わせ最適化問題の中でも難しいとされる問題の代表格となっている。しかしながら、配送計画、基盤穿孔、鋼板の圧延計画など多くの応用を有するため、このような問題を何らかの方法で短時間で処理することが好ましい。
このような巡回セールスマン問題には、制約条件付き巡回セールスマン問題という問題が含まれる。制約条件付き巡回セールスマン問題には、複数のグループ（班とも呼ぶ）で作業する問題が含まれており、この問題は、最後に帰ってくるグループの作業時間を最小化する問題と、全員の作業時間の合計を最小化する問題とを含む。前者は、全体の作業時間を最小化することになる。後者は、総移動距離を最小化し、ガソリン代等の移動経費の削減が可能となる。制約条件としては、巡回する作業場所の順序についての制約である優先度条件、複数のグループが合流して作業を行うことについての制約（合流条件や合流可能条件）などがある。なお、合流条件は、必ず合流して作業するような場合などに設定される。合流可能条件は、合流により作業効率が上がるような場合に設定される条件である。このような制約条件付き巡回セールスマン問題に定式化できる問題には、人員配置問題や、物流問題、配送計画、災害復旧計画問題などがある。
このような巡回セールスマン問題を解くためのアルゴリズムには様々なものがあるが、何らかの方法で定義された巡回路の近傍を探索して解を改善する局所改善法がある。しかしながら、設定される制約条件によっては、従来の局所改善法をそのまま適用できない場合がある。
例えば２点交換アルゴリズムという局所改善法が知られているが、これは巡回路が何らかの方法で図１Ａに示されているように（１，５，６，７，２，４，３）と決定されている状態で、図１Ｂに示すように、任意の２点、例えば作業地点２と作業地点５とを入れ替えてみる。すなわち、（１，２，６，７，５，４，３）という新たな巡回路が得られる。この時に、巡回路長が短くなっていれば、変更後の巡回路（１，２，６，７，５，４，３）を採用し、短くなっていなければ、変更前の巡回路（１，５，６，７，２，４，３）を採用する。このような処理を、巡回路長の短縮ができなくなるまで繰り返すものである。
しかしながら、２グループで優先度条件付きの巡回セールスマン問題になると、単純には２点交換アルゴリズムが適用できなくなる。例えば、図２に示すような優先度条件が規定されているものとする。すなわち、作業地点１における作業１を実行した後に、作業地点２及び作業地点３の作業２及び３を実行し、作業地点５の作業５を実行した後に作業地点６の作業６を実行し、作業地点９の作業９を実行した後に作業地点１０の作業１０を実行することになっている。さらに、何らかの方法にて、グループＡは、作業地点１の作業１と、作業地点２の作業２と、作業地点３の作業３と、作業地点４の作業４と、作業地点１０の作業１０と、作業地点７の作業７とをこの順番で実行することになり、グループＢは、作業地点５の作業５と、作業地点９の作業９と、作業地点８の作業８と、作業地点６の作業６とをこの順番で実行することになったものとする。
このような場合における作業実行状況を図３に模式的に示して説明する。なお、図３では、各作業地点における作業の作業時間はボックスの横方向の長さで表し、横方向の矢印の長さで移動時間を表すものとする。グループＡは、作業１乃至３をこの順で実行するので、優先度条件を満たしている。また、グループＢは、作業５及び作業６を、それらの間に作業９及び作業８を挟んでいるが、優先度条件を満たすように実行している。さらに、グループＢが作業９を先に実行し、グループＡが作業１０を後から実行するようにスケジュールされており、図２に示した優先度条件を満たすように作業を行っている。
このような状況において、例えばグループＢにのみ着目して作業９と作業６とを入れ替えるような２点交換アルゴリズムを実施するものとする。そうすると、図４に示すような作業実行状況のようになる。図４に示すように、グループＡの作業実行状況は図３に示したものと変わらない。また、グループＢのみに着目すると、このような作業順番の入れ替えが行われても、作業５を実施した後に作業６を実施するという優先度条件は満たしている。しかしながら、作業９が後ろに回されているのでグループＡが実施する作業１０が、グループＢが実施する作業９より先に行われるようになるので、全体として優先度条件を満たしていないことになる。このように、全体として優先度条件を満たすためには、２次改善を行わなければならなくなるが、この２次改善がさらに優先度条件を満たさない部分を生じさせる可能性もある。
局所改善法の一例として２点交換アルゴリズムを示したが、他の局所改善法（例えば２−ｏｐｔ（ｋ−ｏｐｔ）法、ｏｒ−ｏｐｔ法、ｋ点交換アルゴリズム、遺伝的アルゴリズム、焼きなまし法、タブー探索法など）でも同様である。
なお、複数車両を用いた配送経路問題の、車両数が低減された解を求めるための技術が公開されている。具体的には、複数の車両が、或る拠点から複数の配送地点に物品を届ける配送計画を作成する方法は、所与の現在の解Ｓの近傍解からなる解集合（Ｎ（Ｓ））について、所与の終了条件に達するまで、局所探索を反復して、Ｓを更新して、最適解Ｓｂｅｓｔを求めるステップを含む。この局所探索において車両数が最も少ない解を探索するステップ、次いで車両数が最も少ない解が複数ある場合には、この複数の解について、下記式（１）で定義される車両ごとの評価値Ｂｋ（ｔ）（ｔ∈Ｎ（Ｓ））の、下記式（２）で定義される車両間のばらつきの少なさを示す指標β（ｔ）が最も小さい解を探索するステップを含む。
Ｂｋ（ｔ）＝Σｉ∈Ｃｋ（ｔ）ｐｉ／Ｍ （１）
β（ｔ）＝１−Σｋ∈σ（ｔ）Ｂｋ（ｔ）ｍ／｜σ（ｔ）｜（２）
しかしながら、上で述べたように局所探索が単純には適用できない場合という問題については開示されていない。他の従来技術でも同様である。
特開２０１０−１１１４５２号公報 特開平１１−３１００９号公報 特開２００３−２６３３５号公報 特開２００６−１８４４３号公報
従って、本発明の目的は、一側面として、複数の作業者グループで複数の作業を少なくとも一部分担して巡回実行する場合に作業順番を決定するような問題に対して一般的な局所改善法を適用可能にするための技術を提供することである。
本技術に係る情報処理方法は、（Ａ）複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理と、（Ｂ）複数の作業者グループの各々について、時間を進めつつ、記憶部に格納されている実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、所定数の作業について設定されている制約条件を満たすか否かを判定することで、複数の作業者グループの各々について、実行予定順番において実行すべき作業を決定し、決定された作業順番についての評価値を算出し、記憶部に格納する第２の処理とを含む。
複数の作業者グループで複数の作業を少なくとも一部分担して巡回実行する場合に作業順番を決定するような問題に対して一般的な局所改善法を適用可能になる。
図１Ａは、２点交換アルゴリズムを説明するための図である。 図１Ｂは、２点交換アルゴリズムを説明するための図である。 図２は、優先度条件の一例を示す図である。 図３は、作業実行状況の一例を示す図である。 図４は、２点交換アルゴリズムによって変更した後の作業実行状況を示す図である。 図５は、第１の実施の形態に係る情報処理装置の機能ブロック図である。 図６は、第１の実施の形態に係る処理の処理フローを示す図である。 図７は、実行予定順番の例を示す図である。 図８Ａは、巡回処理部の処理を模式的に示す図である。 図８Ｂは、巡回処理部の処理を模式的に示す図である。 図８Ｃは、巡回処理部の処理を模式的に示す図である。 図８Ｄは、巡回処理部の処理を模式的に示す図である。 図８Ｅは、巡回処理部の処理を模式的に示す図である。 図８Ｆは、巡回処理部の処理を模式的に示す図である。 図８Ｇは、巡回処理部の処理を模式的に示す図である。 図８Ｈは、巡回処理部の処理を模式的に示す図である。 図９Ａは、記憶部に格納される実行順番のデータを表す図である。 図９Ｂは、記憶部に格納される実行順番のデータを表す図である。 図９Ｃは、記憶部に格納される実行順番のデータを表す図である。 図９Ｄは、記憶部に格納される実行順番のデータを表す図である。 図９Ｅは、記憶部に格納される実行順番のデータを表す図である。 図９Ｆは、記憶部に格納される実行順番のデータを表す図である。 図９Ｇは、記憶部に格納される実行順番のデータを表す図である。 図９Ｈは、記憶部に格納される評価値を表す図である。 図１０は、決定された作業について説明するための図である。 図１１は、変更後の作業予定順番の一例を示す図である。 図１２は、変更後の作業予定順番において決定された作業について説明するための図である。 図１３は、変更後の実行状況を模式的に示す図である。 図１４は、第２の実施の形態における情報処理装置の機能ブロック図である。 図１５は、移動コストテーブルの一例を示す図である。 図１６は、制約条件テーブルの一例を示す図である。 図１７は、処理能力テーブルの一例を示す図である。 図１８Ａは、班管理テーブルの一例を示す図である。 図１８Ｂは、現作業量管理テーブルの一例を示す図である。 図１９は、巡回路管理テーブルの一例を示す図である。 図２０は、第２の実施の形態の処理フローを示す図である。 図２１Ａは、初期設定処理を説明するための図である。 図２１Ｂは、初期設定処理を説明するための図である。 図２１Ｃは、初期設定処理を説明するための図である。 図２２は、巡回時間計算処理の処理フローを示す図である。 図２３は、班管理テーブルの初期状態を示す図である。 図２４は、巡回路管理テーブルの初期状態を示す図である。 図２５は、ステージ処理の処理フローを示す図である。 図２６は、ステージ処理の処理フローを示す図である。 図２７は、ステージ処理の処理フローを示す図である。 図２８は、調整処理の処理フローを示す図である。 図２９は、時間進行処理の処理フローを示す図である。 図３０は、巡回予定路の他の設定方法について説明するための図である。 図３１Ａは、巡回路管理テーブルの巡回時間計算処理完了時の状態を表す図である。 図３１Ｂは、巡回路管理テーブルの更新後の状態を表す図である。 図３２は、２点交換アルゴリズムの一例を示す図である。 図３３Ａは、２点交換アルゴリズムを説明するための図である。 図３３Ｂは、２点交換アルゴリズムを説明するための図である。 図３４は、コンピュータの機能ブロック図である。
［実施の形態１］
本技術の第１の実施の形態に係る情報処理装置１０００の機能ブロック図を図５に示す。情報処理装置１０００は、初期設定処理部１１００と、巡回処理部１２００と、局所改善部１３００と、制御部１４００と、記憶部１５００と、制約データ格納部１６００とを有する。
制約データ格納部１６００は、巡回実行すべき複数の作業について設定されている制約条件についてのデータを格納している。制約条件には、優先条件、合流条件、合流可能条件が含まれる場合もある。また、制約データ格納部１６００は、作業を行う場所間の移動コスト（時間又は距離）についてのデータ、各作業の作業量及び各作業員グループの作業処理能力も格納しているものとする。
制御部１４００は、初期設定処理部１１００、巡回処理部１２００と、局所改善部１３００とに対して、以下のように処理を実施するように制御する。
初期設定処理部１１００は、制約データ格納部１６００に優先度条件が格納されている場合には当該優先度条件を満たすように、各作業者グループについて、これらの複数の作業者グループで巡回実行すべき複数の作業を並べて、実行予定順番を決定し、実行予定順番のデータを記憶部１５００に格納する。
巡回処理部１２００は、各作業者グループについて、時間を進めつつ、実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部１６００に格納されている制約条件を満たすか否かを判断して、各作業者グループについて、実行予定順番において実行すべき作業を決定し、記憶部１５００に格納する。また、巡回処理部１２００は、決定された作業順番（すなわち作業分担）についての評価値（例えば作業者グループについての作業時間及び移動時間の総和、各作業者グループについての作業時間及び移動時間の総和のうち最も長いもの）を算出して、記憶部１５００に格納する。なお、巡回処理部１２００は、時間を進める際には、各作業にかかる時間、作業場所間を移動するのにかかる時間を、制約データ格納部１６００に格納されているデータを用いて計算する。
局所改善部１３００は、制約データ格納部１６００に優先度条件が格納されている場合には当該優先度条件を満たすように、記憶部１５００に格納されている実行予定順番を変更し、変更後の実行予定順番のデータを記憶部１５００に格納する。この局所改善部１３００の処理は、従来の局所改善法のアルゴリズムに従って行われる。
制御部１４００は、変更後の実行予定順番について巡回処理部１２００に処理を実行させ、変更後の実行予定順番についての評価値を算出させる。そして、制御部１４００は、変更後の実行予定順番についての評価値が、それより前に算出された評価値より低くなっているか判断し、評価値が低下していれば、当該評価値、作業順番のデータ及び変更後の実行予定順番などを次処理のためのデータとして、記憶部１５００に格納する。変更後の実行予定順番についての評価値が低下していなければ、制御部１４００は、当該変更後の実行予定順番及び関連データを破棄する。そして、制御部１４００は、終了条件を満たすようになるまで、局所改善部１３００及び巡回処理部１２００に処理を実行させる。
次に、情報処理装置１０００の処理内容を図６乃至図１３を用いて説明する。前提として、作業者グループ数、制約条件、作業を行う場所（スタート地点及びゴール地点を含む）間の移動コスト、各作業の作業量及び各作業員グループの作業処理能力などのデータが制約データ格納部１６００に格納されているものとする。また、スタート地点及びゴール地点は作業場所とは異なる場所が設定されているものとする。スタート地点及びゴール地点は同じであっても良い。
制御部１４００は、初期設定処理部１１００に、各作業者グループについて、全作業者グループで巡回実施すべき所定数の作業についての作業予定順番を決定させ、当該作業予定順番のデータを、記憶部１５００に格納させる（図６：ステップＳ１）。この際、初期設定処理部１１００は、制約データ格納部１６００に優先度条件が格納されている場合には、当該優先度条件を、各作業者グループの作業予定順番において満たすように作業の並びを決定する。例えば、ランダムに作業を並べた上で、優先度条件を満たしていない部分については、優先度条件を満たすように並び替える。
例えば、作業者グループが２つで、図２に示したような優先度条件が設定されており、ある開始地点から移動を開始し、作業地点１の作業１から作業地点１０の作業１０までの作業を２つの作業者グループで実行し、完了後に終了地点に戻る場合を想定する。そうすると、例えば図７に示すような実行予定順番が決定されたものとする。作業者グループＡと作業者グループＢには、それぞれ作業地点１乃至作業地点１０の作業１乃至作業１０が含まれた実行予定順番が決定される。これらの実行予定順番は、各々の中で優先度条件を満たしている。但し、この段階ではいずれの作業を実行するのかについては確定していない。また、本実施の形態では、作業場所（すなわち作業地点）と作業とは１対１対応しているものとする。
次に、制御部１４００は、巡回処理部１２００に対して、以下のような処理を実施させる（ステップＳ３）。すなわち、各作業者グループについて、時間を進めつつ、実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部１６００に格納されている、優先度条件などを含む制約条件を満たすか否かを判断することで、各作業者グループについて、実行予定順番において実行すべき作業を決定し、当該実行すべき作業のデータを、記憶部１５００に格納する。さらに、当該決定された作業順番について評価値を算出し、記憶部１５００に格納する。例えば、評価値は、作業者グループのうち最も長い作業時間及び移動時間であるか、各作業者グループの作業時間及び移動時間の総和である。また、他の作業者グループによって完了してしまっている作業については、再度実行することなくスキップする。
より具体的には、移動時間については、作業場所間の移動コストから特定する。さらに、作業時間については、作業量を作業能力で除することで算出される。このようなデータによって時間が進められる。そして、作業者グループＡについては、作業１を実行することが制約条件を満たしている場合には、作業１の場所に移動する。さらに、作業者グループＢについては、作業５を実行することが制約条件を満たしている場合には、作業５の場所（即ち作業地点５）に移動する。そして、作業者グループＡについては、作業１の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業１を開始する。作業者グループＢについても、作業５の作業開始にあたって合流条件等の制約条件を満たしている場合には、作業５の作業を開始する。すなわち、図８Ａに示すような状態となる。図８Ａ乃至図８Ｈにおいては、図３と同様に、矢印の長さで移動時間を表し、矩形の長さは作業時間を表している。各作業者グループについて、移動先又は実行中の作業については、記憶部１５００に格納しておく。すなわち、図９Ａのようなデータが、記憶部１５００に格納される。
さらに、作業者グループＡについては、作業１を完了すると、作業予定順番において次の作業２を実行することが制約条件を満たしている場合には、作業２の場所に移動する。さらに、作業者グループＡについては、作業２の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業２を開始する。作業者グループＢについては、この期間中は、作業５を実行中である。そうすると、図８Ｂに示すような状態となる。また、記憶部１５００には、図９Ｂに示すようなデータが格納される。
さらに、作業者グループＡについては、作業２を完了すると、作業予定順番において次の作業３を実行することが制約条件を満たしている場合には、作業３の場所に移動する。さらに、作業者グループＡについては、作業３の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業３を開始する。作業者グループＢについては、この期間中は、作業５を実行中である。そうすると、図８Ｃに示すような状態となる。また、記憶部１５００には、図９Ｃに示すようなデータが格納される。
その後、作業者グループＡが作業３を実行中に、作業者グループＢは作業５を完了させる。そうすると、作業者グループＢについて、作業予定順番において次の作業９を実行することが制約条件を満たしている場合には、作業９の場所に移動する。さらに、作業者グループＡについては、作業３を完了すると、作業予定順番において次の作業４を実行することが制約条件を満たしている場合には、作業４の場所に移動する。さらに、作業者グループＡについては、作業４の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業４を開始する。そうすると、図８Ｄに示すような状態となる。また、記憶部１５００には、図９Ｄに示すようなデータが格納される。
その後、作業者グループＢについては、作業９の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業９を開始する。さらに、作業者グループＡについては、作業４が完了すると、作業予定順番において次の作業５を実行することが制約条件を満たしているか判断する。この場合、既に作業５を作業者グループＢにより完了している。従って、作業者グループＡは、作業５の場所（すなわち作業地点５）に移動しない。さらに、作業者グループＡについては、作業予定順番において次の作業９を実行することが制約条件を満たしているか判断する。この場合、既に作業９を作業者グループＢが実行することが確定しており、作業９について合流せず且つ先に移動した作業者グループを優先するという合流条件があれば、この合流条件を満たさないと判定する。従って、作業者グループＡは、作業９の場所（即ち作業地点９）に移動しない。さらに、作業者グループＡについては、作業予定順番において次の作業１０を実行することが制約条件を満たしているか判断する。ここでは作業９を作業１０より先に実施するという優先度条件が設定されているので記憶部１５００のデータ（図９Ｄ）を確認する。この場合、作業９は完了しているので問題ない。従って、作業者グループＡは作業１０の場所（すなわち作業地点１０）に移動する。そうすると、図８Ｅに示すような状態となる。また、記憶部１５００には、図９Ｅに示すようなデータが格納される。
その後、作業者グループＢについては、作業９を完了すると、作業予定順番において次の作業８を実行することが制約条件を満たしている場合には、作業８の場所に移動する。さらに、作業者グループＢについては、作業８の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業８を開始する。一方、作業者グループＡについては、作業１０の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業１０を開始する。そうすると、図８Ｆに示すような状態となる。また、記憶部１５００には、図９Ｆに示すようなデータが格納される。
その後、作業者グループＢについては、作業８を完了すると、作業予定順番において次の作業６を実行することが制約条件を満たしている場合には、作業６の場所に移動する。さらに、作業者グループＡについては、作業１０を完了すると、作業予定順番において次の作業７を実行することが制約条件を満たしている場合には、作業７の場所に移動する。そして、作業者グループＡについては、作業７の作業開始にあたって合流条件などの制約条件を満たしている場合には、作業７を開始する。そうすると、図８Ｇに示すような状態となる。また、記憶部１５００には、図９Ｇに示すようなデータが格納される。
その後、作業者グループＢについては、作業６を完了すると、作業予定順番において以降の作業１０、作業７、作業４、作業１、作業３及び作業２を実行することが制約条件を満たしているか判断する。ここでは、既にこれらの作業を作業者グループＡにより完了している。従って、作業者グループＢは、これらの作業の場所に移動せず、ゴール地点に移動する。
同様に、作業者グループＡについては、作業７を完了すると、作業予定順番において以降の作業８及び作業６を実行することが制約条件を満たしているか判断する。ここでは、既にこれらの作業を作業者グループＢにより完了している。従って、作業者グループＡは、これらの作業の場所に移動せず、ゴール地点に移動する。そうすると、図８Ｈに示すような状態となる。なお、作業者グループＡについては、ゴール地点に矢印が届いていないが、単に作業者グループＢよりも短い時間でゴール地点に到達したことを示している。
このように時間を進めつつ、ステップバイステップで次の作業の場所への移動可否、次の作業場所に到着すると作業開始の是非などを判断して、制約条件を満たしている作業について、各作業者グループについて記憶部１５００に格納する。そうすると、作業分担のデータが記憶部１５００に格納されることになる。なお、図１０に示すように、図７に示した実行予定順番に含まれる作業のうち、丸が付された数字の作業が、実行すべき作業として特定されている。図１０からも分かるように、実行予定順番に含まれていても実施しない作業もあるし、飛び飛びの順番で実施される場合もある。
さらに、巡回処理部１２００は、例えば作業者グループＡ及び作業者グループＢの移動時間及び作業時間の総和を算出することで評価値を求め、又は作業者グループＡの移動時間及び作業時間の総和と作業者グループＢの移動時間及び作業時間の総和のうちいずれか長い方を特定することで評価値を求め、記憶部１５００に格納する。例えば図９Ｈに示すような評価値が、記憶部１５００に格納される。
図６の処理の説明に戻って、制御部１４００は、局所改善部１３００に、記憶部１５００に格納されている、各作業者グループの実行予定順番に対して局所改善法の処理を実施することで実行予定順番を変更させ、記憶部１５００に変更後のデータを格納させる（ステップＳ５）。例えば、２点交換アルゴリズムを実施する。但し、他の局所改善法（例えば２−ｏｐｔ（ｋ−ｏｐｔ）法、ｏｒ−ｏｐｔ法、ｋ点交換アルゴリズム、遺伝的アルゴリズム、焼きなまし法、タブー探索法など）でも良い。この処理においても、制約データ格納部１６００に優先度条件が格納されている場合には、優先度条件については満たすようにする。本実施の形態では、図７に示すように、各作業者グループについて、巡回実行すべき全作業を並べるので、作業者グループ間について優先度条件や合流条件などの制約条件を満たすか否かを確認することなく、従来からある局所改善法のアルゴリズムを適用可能となる。例えば、図１１に示すような変更後の実行予定順番が得られたものとする。作業者グループＢの実行予定順番における作業６及び作業９の順番が入れ替えられている。
その後、制御部１４００は、巡回処理部１２００に、記憶部１５００に格納されている変更後の実行予定順番について、ステップＳ３の処理を実施させる（ステップＳ７）。すなわち、時間を進めつつ、変更後の実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部１６００に格納されている、優先度条件などを含む制約条件を満たすか否かを判断することで、各作業者グループについて、変更後の実行予定順番において実行すべき作業を決定し、当該実行すべき作業のデータを、記憶部１５００に格納する。さらに、当該決定された作業分担について評価値を算出し、記憶部１５００に格納する。
この場合、図１２に示すように、作業者グループＡについては、実行予定順番が変更されなかったにも拘わらず、実行すべき作業は、作業１、作業２、作業３、作業４、作業９及び作業１０となる。また、作業者グループＢについては、変更された実行予定順番に従って、実行すべき作業は、作業５、作業６、作業８及び作業７となる。実行状態は、図１３に模式的に示すようになる。この例では、図８Ｈの作業時間＋移動時間を表す実線ａと、この例における作業時間＋移動時間を表す点線ｂとを比較すると、局所改善法の効果が現れて、最後に帰ってくる作業者グループの作業時間＋移動時間に相当する評価値が小さくなっていることが分かる。
その後、制御部１４００は、基準となる評価値（最初の場合にはステップＳ３で計算された評価値。次回以降は採用されて次の処理のための領域に格納された評価値）と、記憶部１５００に格納されており且つステップＳ７で計算された評価値とを比較して、小さい方のデータを採用する（ステップＳ９）。図１３のような場合には、ステップＳ７で計算された評価値の方が小さくなるので、ステップＳ７で決定された作業分担のデータ及び評価値を、記憶部１５００において次の処理に用いるための領域に格納する。採用しなかったデータについては破棄して良い。但し、履歴を後から参照するためには、保持しておく。
その後、制御部１４００は、処理を終了すべきか判断する（ステップＳ１１）。例えば、評価値が、予め定められた閾値未満になった場合、ステップＳ７の実行回数又は全体の実行時間が閾値を超えた場合、評価値の履歴データを保持している場合には評価値の低下度合いが閾値未満になった場合などに該当するかを判断する。処理を終了すべき場合には、制御部１４００は、記憶部１５００において次の処理に用いるための領域に格納されている作業分担のデータ及び評価値を、出力装置に出力する（ステップＳ１５）。そして処理を終了する。
一方、処理を終了しない場合には、制御部１４００は、ステップＳ９で採用すべきとされた実行予定順番を処理対象に設定して（ステップＳ１３）、ステップＳ５に戻る。すなわち、さらに局所改善法を実施する。
このように、各作業者グループについて、巡回実行すべき全作業を含む実行予定順番をベースに処理を実施することで、一般的な局所改善法のアルゴリズムを適用することができるようになる。さらに、ステップＳ３の処理を実施することで、複雑な制約条件をも取り込んだ形で、作業者グループについての作業分担を適切に特定することもできる。
なお、本実施の形態では、各作業は、対応する作業場所で実行されることを前提としている。すなわち、作業の順番は、巡回する作業場所の順番に相当する。
［実施の形態２］
本技術の第２の実施の形態に係る情報処理装置１００を図１４に示す。
情報処理装置１００は、初期設定処理部１０と、巡回処理部２０と、局所最適化部３０と、制御部４０と、データ格納部５０と、条件データ格納部６０と、出力装置７０とを有する。
条件データ格納部６０は、図１５乃至図１７に示すようなデータを格納する。例えば図１５の移動コストテーブルに示すように、開始地点Ｐ0及び作業地点Ｐ1乃至ＰN間の移動コストとして移動時間のデータが格納される。なお、開始地点Ｐ0から移動を開始して、作業が全て完了した場合には、開始地点Ｐ0に戻るものとする。また、例えば図１６の制約条件テーブルに示すように、各作業について、作業量と、親リストと、子リストと、最低作業員数と、合流条件及び合流可能条件とが格納される。図１６は、作業数が１０である場合の例であるが、一般的にはＮ個の作業について上で述べたデータを用意する。また、親リスト及び子リストによって優先度条件を規定しており、図２のような優先度条件を表すと図１６に示すような子リスト及び親リストの設定になる。また、最低作業員数については、「１」であれば合流せずとも実行でき、合流不可であれば１班で実行することになる。また、合流条件及び合流可能条件については、該当する条件を設定する。さらに、図１７の処理能力テーブルに示すように、班ごとに、単位時間当たりの作業の処理能力についても格納する。作業量／処理能力によって作業時間が算出できる。
データ格納部５０は、処理途中及び処理結果のデータを格納する。例えば、図１８Ａの班管理テーブルに示すように、各班について、状態と、現在位置と、残時間とが格納される。状態は、作業開始前を表す初期、ある作業地点から他の作業地点への移動中を表す移動中、ある地点に到着し且つ作業を実行している状態を表す作業中、優先度や合流条件などで作業地点に到着したが作業を開始できない状態を表す待機中、作業を完了して開始地点に戻った状態を表す完了が含まれる。位置は、状態が移動中であればその行き先を表し、それ以外は現在その班が存在する地点を表す。残時間は、移動又は作業が完了するまでの時間を表す。但し、状態が完了の場合には、その班の作業時間及び移動時間の総和である。また、図１８Ｂの現作業量管理テーブルに示すように、データ格納部５０は、現作業量についても管理する。すなわち、初期的には、図１６に示した制約条件テーブルに含まれる作業量を、現作業量として設定するが、作業が進むと現作業量が減少する。
さらに、図１９の巡回路管理テーブルに示すようなデータもデータ格納部５０に格納する。図１９の例では、これまでの巡回路のうちの最適巡回路についてのデータと、現在の巡回路についてのデータとが格納されるようになっている。それぞれについて、班ごとに、以下の配列における現インデックスを表すＩＤと、巡回すべき地点の配列（例えば１乃至Ｎ）とを含む。
制御部４０は、初期設定処理部１０、巡回処理部２０と、局所最適化部３０とに対して、以下のように処理を実施するように制御する。
初期設定処理部１０は、条件データ格納部６０の制約条件テーブルに優先度条件が設定されている場合には当該優先度条件を満たすように、各班について、巡回すべき全作業場所を並べて、巡回予定路を決定し、巡回予定路のデータをデータ格納部５０に格納する。
巡回処理部２０は、各班について、時間を進めつつ、巡回予定路に係る各作業の作業場所への移動及び当該作業の開始が、条件データ格納部６０に格納されている制約条件を満たすか否かを判断して、各班について、巡回予定路における作業地点を決定し、データ格納部５０に格納されている巡回路管理テーブルに登録する。また、巡回処理部２０は、決定された巡回順番についての評価値としての時間（班管理テーブルにおける残時間の値）を更新して、データ格納部５０の班管理テーブルに登録する。なお、巡回処理部２０は、時間を進める際には、各作業にかかる時間、作業地点間を移動するのにかかる時間を、条件データ格納部６０に格納されているデータを用いて計算する。
局所最適化部３０は、条件データ格納部６０における制約条件テーブルに優先度条件が登録されている場合には当該優先度条件を満たすように、データ格納部５０に格納されている巡回予定路を変更し、変更後の巡回予定路のデータをデータ格納部５０に格納する。この局所最適化部３０の処理は、従来の局所改善法のアルゴリズムに従って行われる。
制御部４０は、変更後の巡回予定路について巡回処理部２０に処理を実行させ、変更後の巡回予定路についての評価値（時間）を算出させる。そして、制御部４０は、変更後の巡回予定路についての評価値が、それより前に算出された評価値より低くなっているか判断し、評価値が低下していれば、当該評価値、巡回順番（又は作業の実行順番）のデータ及び変更後の巡回予定路などを次処理のためのデータとして、データ格納部５０に格納する。変更後の巡回予定路についての評価値が低下していなければ、制御部４０は、当該変更後の巡回予定路及び関連データを破棄する。そして、制御部４０は、終了条件を満たすようになるまで、局所最適化部３０及び巡回処理部２０に処理を実行させる。
次に、図２０乃至図３３Ｂを用いて、図１４に示した情報処理装置１００の処理内容について説明する。まず、制御部４０は、初期設定処理部１０に、初期設定処理を実施させる（図２０：ステップＳ１０１）。初期設定処理には、初期的な巡回予定路を生成する処理が含まれる。
初期的な巡回予定路を生成する処理は、例えば２つの方法のいずれかで行われる。第１の方法は、例えば各班について巡回実行すべき作業をランダムに並べて、並べられた作業に従って対応する作業地点を並べた初期の巡回予定路を生成する。そして、条件データ格納部６０における制約条件テーブルに優先度条件が設定されている場合には、班ごとに、当該優先度条件を満たすように例えば順番を入れ替えるような処理を実施する。第２の方法は、他の手法で生成された巡回路（すなわち解）を初期値にして、各班について巡回予定路を生成する方法である。例えば、図２１Ａに示すような解が得られている場合、各班について優先度条件を満たさない部分があるか探索して、満たさない部分があれば、直前に親地点を挿入するようにする。図２１Ａの場合、班１において、地点Ｐ10の前に親地点が存在していないので、図２１Ｂに示すように、直前に親地点Ｐ9を挿入する。残りについては、優先度条件を満たすようにランダムに作業地点を設定する。図２１Ｃに示すように、班１については、８番目乃至１０番目については、残余の作業地点を優先度条件を満たすように挿入している。具体的には、作業地点Ｐ5は親地点で作業地点Ｐ6は子地点であるから、この順番については維持する。一方、班２については、残余の作業地点には優先度条件が関係するものが含まれていないので、ランダムに作業地点を付加する。なお、図２１Ａ乃至図２１Ｃの例では作業地点を並べることで巡回予定路を生成しているが、作業を同様の手順で並べるようにして作業予定順番を生成しても良い。この作業予定順番から巡回予定路を生成しても良い。すなわち、本実施の形態においても、作業場所（すなわち作業地点）と作業とは１対１対応している。
次に、制御部４０は、巡回処理部２０に、巡回時間計算処理を実施させる（ステップＳ１０３）。巡回時間計算処理については、図２２乃至図３０を用いて説明する。
まず、巡回処理部２０は、班管理テーブル、巡回路管理テーブルを初期化すると共に、現在時刻を０に設定する（図２２：ステップＳ１１１）。班管理テーブルについては、図２３に示すように、状態を「初期」に設定し、現在位置を開始地点Ｐ0に設定し、指示位置を「１」に設定し、残時間を「０」に設定する。巡回路管理テーブルについては、図２４に示すように、現巡回路についての各班のＩＤを「０」に初期化する。なお、現作業量管理テーブルにも制約条件テーブルにおける作業量のデータをコピーして格納する。
その後、巡回処理部２０は、班管理テーブルにおいて全班の状態が完了に設定されているか判断する（ステップＳ１１３）。まだ完了となっていない班が存在する場合には、巡回処理部２０は、ステージ処理を実施する（ステップＳ１１５）。ステージ処理については、図２５乃至図２７を用いて説明する。なお、ステージとは、次のイベントが発生するまでの最小時間を表している。具体的には、ある班の移動が完了するまで、又は作業が完了するまでである。
ステージ処理において、巡回処理部２０は、班のカウンタであるｉを１に初期化し（図２５：ステップＳ１３１）、ｉが班の最大値Ｍ以下であるか判断する（ステップＳ１３３）。ｉがＭを超えている場合には、呼び出し元の処理に戻る。
一方、ｉがＭ以下であれば、巡回処理部２０は、班ｉの残時間が０であり且つ状態≠「完了」且つ状態≠「待機中」であるかを、班管理テーブルのデータから判断する（ステップＳ１３５）。班ｉの残時間が０というのは、移動又は作業が完了した状態であり、状態≠「完了」であるというのは、班ｉが開始地点に戻っていないということであり、状態≠「待機中」であるというのは、班ｉが他の班の作業の完了を待機している状態ではないということである。このような条件を満たしていない場合には、端子Ａを介して図２６の処理に移行する。
一方、このような条件を満たしている場合には、巡回処理部２０は、班ｉの状態＝「移動中」であるか判断する（ステップＳ１３７）。状態＝「移動中」であれば端子Ｂを介して図２７の処理に移行する。一方、状態＝「移動中」でなければ、状態＝「作業中」であり、班ｉが実行していたある作業が完了したことになる。そうすると、巡回処理部２０は、制約条件テーブルに規定されている制約条件に従って、巡回予定路［ｉ，指示位置］の作業地点に移動可能であるかを判断する（ステップＳ１３９）。巡回予定路［ｉ，指示位置］の作業地点に移動可能かどうかについては、まず合流条件又は合流可能条件を満たしているかを判断する。
例えば、先に移動した班があればその班を優先し、合流可能条件が設定されていれば合流可能条件を満たしているかを判断する。もし、「合流を許さない」という合流条件が設定されていれば、最初に移動を開始した班が移動し、それ以外は「移動不可」と判断する。他の班が作業を完了している場合にも移動不可と判断する。また、優先度制約等のために他の班の作業を待つことを許すか否かについての待機オプションが設定される場合もある。この場合には、合流条件を満たしているが、直ぐには実行できない作業であっても待機可能と設定されていれば、移動可能と判断する。
移動不能と判定された場合には、巡回処理部２０は、班管理テーブルにおける班ｉの指示位置を１インクリメントし（ステップＳ１４３）、指示位置が作業の数Ｎ以下であるかを判断する（ステップＳ１４５）。指示位置が作業の数Ｎ以下であればステップＳ１３９に戻る。一方、指示位置が作業の数Ｎを超えた場合には、巡回処理部２０は、班管理テーブルにおける現在位置を変数Ｐに設定し、この現在位置に開始地点Ｐ0を設定する（ステップＳ１４７）。すなわち、これ以上作業を実行せずに開始地点Ｐ0に戻ることになる。そして端子Ｃを介して図２６の処理に移行する。
これに対して、ステップＳ１３９で巡回予定路［ｉ，指示位置］に移動可能と判定された場合、巡回処理部２０は、変数Ｐに現在位置を設定し、巡回予定路［ｉ，指示位置］を現在位置に設定し、指示位置を１インクリメントし、巡回路管理テーブルにおいて現巡回路［ｉ］．ＩＤ（現巡回路の行において班ｉのＩＤ）を１インクリメントし、現巡回路［ｉ］．巡回路［ＩＤ］（現巡回路の行において班ｉの巡回路［ＩＤ］の列）に現在位置を設定する（ステップＳ１４１）。すなわち、次の移動先を巡回路［ＩＤ］に格納している。その後端子Ｃを介して図２６の処理に移行する。
端子Ｃ以降の処理を図２６を用いて説明する。巡回処理部２０は、班管理テーブルにおける状態を「移動中」に変更し、班管理テーブルにおける残時間に移動コストテーブルにおける変数Ｐと現在位置との間の移動時間を設定する（ステップＳ１４９）。そして、巡回処理部２０は、ｉを１インクリメントする（ステップＳ１５１）。その後端子Ｄを介して図２５のステップＳ１３３に戻る。
一方、端子Ｂ以降の処理を図２７を用いて説明する。巡回処理部２０は、班管理テーブルにおける現在位置が開始地点Ｐ0であるか判断する（ステップＳ１５３）。現在位置がＰ0であれば、巡回処理部２０は、班管理テーブルにおいて、状態を完了に設定し、残時間に現在時刻を設定する（ステップＳ１５５）。そして端子Ａを介して図２６のステップＳ１５１に移行する。一方、現在位置が開始地点Ｐ0ではない場合には、巡回処理部２０は、現在位置における作業について作業開始が可能であるか判断する（ステップＳ１５７）。作業が開始可能かは、優先度条件が設定されていれば親の作業が全て完了しているか否かで判断される。さらに、現在位置において、状態が「待機中」又は「作業中」の人数が、自班を合わせて「最低作業員数」以上となっているかを判断する。このような条件を満たしていれば、作業開始可能と判断される。作業開始可能であれば、巡回処理部２０は、班管理テーブルにおける班ｉの状態を作業中に変更する（ステップＳ１５９）。そして端子Ａを介して図２６のステップＳ１５１に移行する。一方、作業開始不可能と判断された場合には、巡回処理部２０は、班管理テーブルにおける班ｉの状態を待機中に設定する（ステップＳ１６１）。そして端子Ａを介して図２６のステップＳ１５１に移行する。
このようにすれば、各班について移動を開始したり作業を開始したりすることの是非を判断することができる。
図２２の処理の説明に戻って、巡回処理部２０は、次に調整処理を実施する（ステップＳ１１７）。調整処理については、図２８を用いて説明する。実際には「同時に」状態変更が行われるはずであるが、処理フローでは班１から順番に状態変更を行うことになるため、状態変更に時間的なずれが発生してしまう可能性がある。例えば、最低作業員数「２」の作業地点に同時に２つの班が到着した場合、作業を開始できるはずだが、上で述べた処理ではその点については判断できないので「待機中」のままになってしまう。そこで、以下に述べる処理を実施して、作業を開始させるようにする。
まず、巡回処理部２０は、班のカウンタｉを１に初期化する（ステップＳ１７１）。そして、巡回処理部２０は、ｉが班の最大値Ｍ以下であるか判断する（ステップＳ１７３）。ｉがＭ以下であれば、巡回処理部２０は、班管理テーブルにおける班ｉの状態が待機中であるか判断する（ステップＳ１７５）。状態が待機中でなければステップＳ１８１に移行する。一方、状態が待機中であれば、巡回処理部２０は、現在位置の作業が作業開始可能であるか判断する（ステップＳ１７７）。この判断はステップＳ１５７と同じである。現在位置の作業が作業開始不能である場合にはステップＳ１８１に移行する。
一方、現在位置の作業が作業開始可能である場合には、巡回処理部２０は、班ｉの状態を作業中に変更し（ステップＳ１７９）、ｉを１インクリメントする（ステップＳ１８１）。その後ステップＳ１７３に戻る。
一方、ステップＳ１７３でｉがＭを超えたと判断された場合には、巡回処理部２０は、ｉを１に初期化し（ステップＳ１８３）、ｉが班の最大値Ｍ以下であるか判断する（ステップＳ１８５）。ｉがＭを超えている場合には、呼び出し元の処理に戻る。
一方、ｉがＭ以下であれば、巡回処理部２０は、班管理テーブルにおける班ｉの状態が作業中であるか判断する（ステップＳ１８７）。状態が作業中ではない場合には、ステップＳ１９１に移行する。一方、状態が作業中であれば、巡回処理部２０は、（班ｉにおける作業地点における作業量）／総処理能力（班ｉの作業位置で作業中の班の処理能力の総和）を残時間に設定する（ステップＳ１８９）。その後、巡回処理部２０は、ｉを１インクリメントする（ステップＳ１９１）。そして、処理はステップＳ１８５に戻る。
図２２の処理の説明に戻って、巡回処理部２０は、時間進行処理を実施する（ステップＳ１１９）。時間進行処理については、図２９を用いて説明する。
まず、巡回処理部２０は、班管理テーブルにおいて残時間の最小値を抽出してＴに設定し、現在時刻にＴを加算して時間を進める（図２９：ステップＳ２０１）。また、巡回処理部２０は、班のカウンタｉを１に初期化する（ステップＳ２０３）。さらに、巡回処理部２０は、ｉが班の数Ｍ以下であるか判断する（ステップＳ２０５）。ｉがＭを超えた場合には呼び出し元の処理に戻る。一方、ｉがＭ以下であれば、巡回処理部２０は、班管理テーブルにおいて班ｉの状態が移動中又は作業中であるか判断する（ステップＳ２０７）。状態が移動中又は作業中以外であれば、ステップＳ２１５に移行する。一方、状態が移動中又は作業中であれば、巡回処理部２０は、班ｉの残時間をＴだけ少なくする（ステップＳ２０９）。さらに、巡回処理部２０は、班ｉの状態が作業中であるか判断する（ステップＳ２１１）。作業中でない場合には、ステップＳ２１５に移行する。
一方作業中である場合には、巡回処理部２０は、班ｉがいる作業地点の作業量を、Ｔ×（班ｉの処理能力）だけ削減する（ステップＳ２１３）。そして、巡回処理部２０は、ｉを１インクリメントする（ステップＳ２１５）。その後ステップＳ２０５に戻る。
このようにして時間をステップバイステップで進行させて、各班の状態を遷移させつつ、制約条件に従って移動先を決定してゆく。
図２２の処理の説明に戻って、ステップＳ１１３で全班の状態が完了となっていると判断された場合には、巡回処理部２０は、現巡回路の評価を、全班の移動時間＋作業時間のうち最長のもので行うようになっているかを判断する（ステップＳ１２１）。現巡回路の評価を、全班の移動時間＋作業時間のうち最長のもので行うようになっている場合には、巡回処理部２０は、評価値のための変数Ｔに現在時刻を設定する（ステップＳ１２３）。そして呼び出し元の処理に戻る。変数Ｔはデータ格納部５０に格納されているものとする。
一方、現巡回路の評価を、全班の移動時間＋作業時間のうち最長のもので行うようになっていない場合には、巡回処理部２０は、変数Ｔに、全班の残時間の合計を設定する（ステップＳ１２５）。残時間には完了時の現在時刻が設定されているので、この時間を用いて、全班の移動時間＋作業時間の総和を求めるものである。そして呼び出し元の処理に戻る。このようにして現巡回路の評価値が得られたことになる。
なお、評価値として全班の移動時間＋作業時間の総和を求める場合には、巡回予定路において、次の作業地点には移動せずに開始地点に戻ることを表す「０」を追加するものとする。例えば図３０に示すように、初期的には最後に「０」を追加する。但し、他の制約条件を無視してどの位置にも配置して良いものとする。なお、処理自体は基本的に上で述べたものと同様であるが、「０」の影響で全体の巡回が完了せずに、全班が作業を完了した場合には、評価値が無限大になるようにする。又は、最後に「０」を選択することになった班は、この「０」を無視して残りの作業を実施するものとして、評価値については上で述べた処理のとおりに計算するものとする。
図２０の処理の説明に戻って、制御部４０は、ｔoptに変数Ｔの値を設定し、さらに、巡回路管理テーブルにおいて、現巡回路のデータを、最適巡回路の領域に設定する（ステップＳ１０５）。初期的には、ステップＳ１０３で生成された現巡回路を最適であるものとして設定する。
例えば、上で述べた処理を行うと図３１Ａに示すようなデータが、巡回路管理テーブルに格納される。すなわち、現巡回路の行にデータが設定される。本ステップでは、現巡回路のデータを、最適巡回路の行にコピーするので、図３１Ｂに示すような状態になる。
その後、制御部４０は、終了条件を満たしているか判断する（ステップＳ１０７）。例えば、処理を開始してからの時間が、所定の時間を経過しているか、ｔoptが予め定められた閾値を下回っているか、例えば一定時間又は一定繰り返し回数ｔoptが所定値以上低下しない場合などは、終了条件を満たしているものと判断する。終了条件を満たしている場合には、制御部４０は、データ格納部５０に格納されている巡回路管理テーブルにおける最適巡回路の領域のデータを、出力装置７０に出力する（ステップＳ１１０）。そして処理を終了する。評価値ｔoptを出力するようにしても良い。
一方、終了条件を満たしていない場合には、制御部４０は、局所最適化部３０等に局所最適化処理を実施させる（ステップＳ１０９）。ステップＳ１０９が終了するとステップＳ１０７に戻る。局所最適化処理については、上でも述べたように従来技術をそのまま適用可能である。ここでは２点交換アルゴリズムについて図３２乃至図３３Ｂを用いて説明する。
まず、局所最適化部３０は、データ格納部５０に格納されている巡回予定路の仮変更を実施し、変更後の巡回予定路をデータ格納部５０に格納する（図３２：ステップＳ２２１）。２点交換アルゴリズムの場合には、班番号をランダムに１つ決定し変数ｇに設定する。さらに、これまでに選択していないインデックスの組み合わせ（ｉ，ｊ）を選択する。そして、巡回予定路の班ｇにおけるｉ番目の作業地点とｊ番目の作業地点とを入れ替える。具体的には、図３３Ａに示すような巡回予定路（一部）が存在しており、ｇ＝１、ｉ＝１、ｊ＝３と設定されると、図３３Ｂに示すように、１番目の作業地点と３番目の作業地点とが入れ替えられる。
そして、局所最適化部３０は、各班について、制約条件テーブルに規定されている優先度条件を満たすか判断する（ステップＳ２２３）。優先度条件を満たしていない場合には、ステップＳ２２１に戻って巡回予定路の変更を行う。一方、優先度条件を満たしている場合には、局所最適化部３０は、巡回処理部２０に、仮変更後の巡回予定路に対して巡回路時間計算処理を実施するように要求する（ステップＳ２２５）。そうすると、巡回処理部２０は、上で述べた巡回路時間計算処理を実施する。
ステップＳ２２５が終了して処理結果がデータ格納部５０に格納されると、制御部４０は、ステップＳ２２５で算出されたＴがｔoptより小さいか判断する（ステップＳ２２７）。Ｔがｔopt以上である場合には、制御部４０は、ステップＳ２２１で実施した仮変更後の巡回予定路については破棄する（ステップＳ２３３）。そして呼び出し元の処理に戻る。
一方、Ｔがｔoptより小さい場合には、制御部４０は、巡回路管理テーブルにおいて、最適巡回路のデータを、現巡回路のデータで更新する（ステップＳ２２９）。ステップＳ５の処理と同様である。さらに、制御部４０は、Ｔの値をｔoptに設定する（ステップＳ２３１）。そして呼び出し元の処理に戻る。
以上のような処理を実施することで、すなわち局所探索を行うことで、ｔoptが小さい値となる巡回路（作業分担）が得られるようになる。
なお、局所改善法のアルゴリズムは種々存在しており、本実施の形態のような構成を採用することで複数班で作業を行う巡回セールスマン問題を取り扱うことができない局所改善法のアルゴリズムでも採用することができる。
さらに、様々な制約条件が設定されても、巡回時間計算処理において移動可能か、作業開始可能かの判断によって吸収することができる。移動コストについても、固定的ではなく、時間に応じて変化するような移動コストについても移動コストテーブルを切り替えることで対処できる。さらに、休憩時間を考慮に入れることも可能である。
なお、１つの初期的な巡回予定路について局所最適化を繰り返すのではなく、多数の初期的な巡回予定路について局所最適化を繰り返すようにしても良い。
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、機能ブロック図は一例であって必ずしも実際のプログラムモジュール構成とは一致しない場合もある。さらに、処理フローについても、処理結果が変わらない限り、処理順番を入れ替えたり、並列実行するようにしても良い。複数台のコンピュータを用いて機能分担を行う場合もある。
また、上で述べた例では、問題設定において開始地点と終了地点が同じとしていたが、これは一例にすぎず、異なるようにしても良い。さらに、開始地点を固定にしなくても良い。
なお、上で述べた情報処理装置１００及び１０００は、コンピュータ装置であって、図３４に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
以上述べた本実施の形態をまとめると、以下のようになる。
本実施の形態に係る情報処理方法は、（Ａ）複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１のステップと、（Ｂ）複数の作業者グループの各々について、時間を進めつつ、記憶部に格納されている実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、所定数の作業について設定されている制約条件を満たすか否かを判定することで、複数の作業者グループの各々について、実行予定順番において実行すべき作業を決定し、決定された作業順番についての評価値を算出し、記憶部に格納する第２のステップとを含む。
複数の作業者グループの各々について、はじめから実行する作業順番を決めてしまうと、制約条件によっては一般的な局所改善法のアルゴリズムを適用できなくなる。このように、各作業者グループについて、実行すべき全作業について実行予定順番を決定すれば、作業者グループ間について制約条件を満たすような処理を行わずに済むため、一般的な局所改善法のアルゴリズムを適用可能になる。さらに、最終的な作業の実行順番については、時間を進めつつ、制約条件を考慮した上で決定しているので、複雑な制約条件についても取り扱うことができる。なお、作業と作業場所が一対一対応していれば、作業場所の巡回順番についての処理を行うのと同じである。なお、既に他の作業グループが実行完了した作業については、実行予定順番において実行せずにスキップする。
本情報処理方法は、（Ｃ）記憶部に格納されている実行予定順番の一部に対して、所定のルールに従って変更を加え、記憶部に変更後の実行予定順番を格納する第３のステップと、（Ｄ）記憶部に格納されている変更後の実行予定順番について、上記第２のステップを実行する第４のステップと、（Ｅ）第４のステップにおいて算出された評価値が、第２のステップにおいて算出された評価値より小さい場合に、第４のステップにおいて算出された評価値と第４のステップにおいて決定された実行順番と変更後の実行予定順番とを、記憶部における次処理のための領域に格納する第５のステップとをさらに含むようにしても良い。第３のステップにおける所定のルールには、様々なものを採用することができ、作業者グループ間で制約条件を満たすことができないものでもよい。
さらに、本情報処理方法においては、第３のステップ、第４のステップ及び第５のステップを、算出された評価値が所定の値未満になるという第１の条件、第１のステップ乃至第５のステップの実行時間が所定時間を超えたという第２の条件、評価値の変化が閾値未満で且つ当該状態が一定時間継続されるという第３の条件のいずれかが満たされるまで繰り返すようにしてもよい。このようにすれば、各作業者グループについて、より好ましい、作業の実行順番を得ることができるようになる。
なお、上で述べた第２のステップにおいては、複数の作業者グループの各々について、作業状態と、移動先又は作業場所とを時間経過に応じて記憶部に格納して管理するようにしてもよい。さらに、複数の作業者グループの各々について、所定数の作業のうち実行することが決定された作業の識別子又は当該作業の作業場所を順番に記憶部に格納して管理するようにしてもよい。
さらに、上で述べた第１のステップにおいて、制約データ格納部に優先度条件のデータが格納されている場合には、当該優先度条件を満たすように実行予定順番を決定するようにしても良い。同様に、第３のステップにおいて、制約データ格納部に優先度条件のデータが格納されている場合には、当該優先度条件を満たすように変更後の実行予定順番を決定するようにしても良い。
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
（付記１）
複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、前記複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理と、
前記複数の作業者グループの各々について、時間を進めつつ、前記記憶部に格納されている前記実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、前記所定数の作業について設定されている制約条件を満たすか否かを判定することで、前記複数の作業者グループの各々について、前記実行予定順番において実行すべき作業を決定し、決定された作業順番についての評価値を算出し、前記記憶部に格納する第２の処理と、
を、コンピュータに実行させるためのプログラム。
（付記２）
前記記憶部に格納されている前記実行予定順番の一部に対して、所定のルールに従って変更を加え、前記記憶部に変更後の実行予定順番を格納する第３の処理と、
前記記憶部に格納されている前記変更後の実行予定順番について、前記第２の処理を実行する第４の処理と、
前記第４の処理によって算出された評価値が、前記第２の処理によって算出された評価値より小さい場合に、前記第４の処理によって算出された評価値と前記第４の処理において決定された前記実行順番と前記変更後の実行予定順番とを、前記記憶部における次処理のための領域に格納する第５の処理と、
をさらに、前記コンピュータに実行させるための付記１記載のプログラム。
（付記３）
前記第３の処理、前記第４の処理及び前記第５の処理を、算出された前記評価値が所定の値未満になるという第１の条件、前記第１の処理乃至前記第５の処理の実行時間が所定時間を超えたという第２の条件、前記評価値の変化が閾値未満で且つ当該状態が一定時間継続されるという第３の条件のいずれかが満たされるまで繰り返す
付記２記載のプログラム。
（付記４）
前記第２の処理においては、
前記複数の作業者グループの各々について、作業状態と、移動先又は作業場所とを時間経過に応じて前記記憶部に格納して管理し、
前記複数の作業者グループの各々について、前記所定数の作業のうち実行することが決定された作業の識別子又は当該作業の作業場所を順番に前記記憶部に格納して管理する
付記１乃至３のいずれか１つ記載のプログラム。
（付記５）
前記第１の処理において、前記制約データ格納部に優先度条件のデータが格納されている場合には、当該優先度条件を満たすように前記実行予定順番を決定する
付記１乃至４のいずれか１つ記載のプログラム。
（付記６）
前記第３の処理において、前記制約データ格納部に優先度条件のデータが格納されている場合には、当該優先度条件を満たすように前記変更後の実行予定順番を決定する
付記１乃至４のいずれか１つ記載のプログラム。
（付記７）
複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、前記複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理部と、
前記複数の作業者グループの各々について、時間を進めつつ、前記記憶部に格納されている前記実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、前記所定数の作業について設定されている制約条件を満たすか否かを判定することで、前記複数の作業者グループの各々について、前記実行予定順番において実行すべき作業を決定し、決定された作業順番についての評価値を算出し、前記記憶部に格納する第２の処理部と、
を有する情報処理装置。
（付記８）
複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、前記複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理と、
前記複数の作業者グループの各々について、時間を進めつつ、前記記憶部に格納されている前記実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、前記所定数の作業について設定されている制約条件を満たすか否かを判定することで、前記複数の作業者グループの各々について、前記実行予定順番において実行すべき作業を決定し、決定された作業順番についての評価値を算出し、前記記憶部に格納する第２の処理と、
を、コンピュータが実行する情報処理方法。
１０００ 情報処理装置
１１００ 初期設定処理部
１２００ 巡回処理部
１３００ 局所改善部
１４００ 制御部
１５００ 記憶部
１６００ 制約データ格納部
１００ 情報処理装置
１０ 初期設定処理部
２０ 巡回処理部
３０ 局所最適化部
４０ 制御部
５０ データ格納部
６０ 条件データ格納部

Claims (4)

  1. 複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、前記複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理と、
    前記複数の作業者グループの各々について、時間を進めつつ、前記記憶部に格納されている前記実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、前記所定数の作業について設定されている制約条件を満たすか否かを判定し、前記所定数の作業のうち作業場所への移動及び作業の開始が前記制約条件を満たす作業を前記実行予定順番において実行すべき作業として決定し、決定された作業順番についての評価値を算出し、前記記憶部に格納する第２の処理と、
    前記記憶部に格納されている前記実行予定順番の一部に対して、所定のルールに従って変更を加え、前記記憶部に変更後の実行予定順番を格納する第３の処理と、
    前記記憶部に格納されている前記変更後の実行予定順番について、前記第２の処理を実行する第４の処理と、
    前記第４の処理によって算出された評価値が、前記第２の処理によって算出された評価値より小さい場合に、前記第４の処理によって算出された評価値と前記第４の処理において決定された前記作業順番と前記変更後の実行予定順番とを、前記記憶部における次処理のための領域に格納する第５の処理と、
    を、コンピュータに実行させるためのプログラム。
  2. 前記第３の処理、前記第４の処理及び前記第５の処理を、算出された前記評価値が所定の値未満になるという第１の条件、前記第１の処理乃至前記第５の処理の実行時間が所定時間を超えたという第２の条件、前記評価値の変化が閾値未満で且つ当該状態が一定時間継続されるという第３の条件のいずれかが満たされるまで繰り返す
    請求項１記載のプログラム。
  3. 複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、前記複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理部と、
    前記複数の作業者グループの各々について、時間を進めつつ、前記記憶部に格納されている前記実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、前記所定数の作業について設定されている制約条件を満たすか否かを判定し、前記所定数の作業のうち作業場所への移動及び作業の開始が前記制約条件を満たす作業を前記実行予定順番において実行すべき作業として決定し、決定された作業順番についての評価値を算出し、前記記憶部に格納する第２の処理部と、
    前記記憶部に格納されている前記実行予定順番の一部に対して、所定のルールに従って変更を加え、前記記憶部に変更後の実行予定順番を格納する第３の処理部と、
    前記記憶部に格納されている前記変更後の実行予定順番について、実行すべき作業を決定する処理及び評価値を算出する処理を、前記第２の処理部に実行させる第４の処理部と、
    前記第４の処理部によって算出された評価値が、前記第２の処理部によって算出された評価値より小さい場合に、前記第４の処理部によって算出された評価値と前記第４の処理部によって決定された前記作業順番と前記変更後の実行予定順番とを、前記記憶部における次処理のための領域に格納する第５の処理部と、
    を有する情報処理装置。
  4. 複数の作業者グループで少なくとも一部を分担して巡回実行すべき所定数の作業を、前記複数の作業者グループの各々について並べることで、実行予定順番を決定し、当該実行予定順番を記憶部に格納する第１の処理と、
    前記複数の作業者グループの各々について、時間を進めつつ、前記記憶部に格納されている前記実行予定順番に従って各作業の作業場所への移動及び当該作業の開始が、制約データ格納部に格納されている、前記所定数の作業について設定されている制約条件を満たすか否かを判定し、前記所定数の作業のうち作業場所への移動及び作業の開始が前記制約条件を満たす作業を前記実行予定順番において実行すべき作業として決定し、決定された作業順番についての評価値を算出し、前記記憶部に格納する第２の処理と、
    前記記憶部に格納されている前記実行予定順番の一部に対して、所定のルールに従って変更を加え、前記記憶部に変更後の実行予定順番を格納する第３の処理と、
    前記記憶部に格納されている前記変更後の実行予定順番について、前記第２の処理を実行する第４の処理と、
    前記第４の処理によって算出された評価値が、前記第２の処理によって算出された評価値より小さい場合に、前記第４の処理によって算出された評価値と前記第４の処理において決定された前記作業順番と前記変更後の実行予定順番とを、前記記憶部における次処理のための領域に格納する第５の処理と、
    を、コンピュータが実行する情報処理方法。
JP2011158552A 2011-07-20 2011-07-20 巡回路決定についてのプログラム、方法及び装置 Expired - Fee Related JP5772332B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2011158552A JP5772332B2 (ja) 2011-07-20 2011-07-20 巡回路決定についてのプログラム、方法及び装置
US13/527,824 US20130024227A1 (en) 2011-07-20 2012-06-20 Information processing technique for determining traveling route

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2011158552A JP5772332B2 (ja) 2011-07-20 2011-07-20 巡回路決定についてのプログラム、方法及び装置

Publications (2)

Publication Number Publication Date
JP2013025509A JP2013025509A (ja) 2013-02-04
JP5772332B2 true JP5772332B2 (ja) 2015-09-02

Family

ID=47556411

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2011158552A Expired - Fee Related JP5772332B2 (ja) 2011-07-20 2011-07-20 巡回路決定についてのプログラム、方法及び装置

Country Status (2)

Country Link
US (1) US20130024227A1 (ja)
JP (1) JP5772332B2 (ja)

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP6097105B2 (ja) * 2013-03-15 2017-03-15 オムロン株式会社 情報処理装置、および作業員割当方法
JP5847986B2 (ja) * 2013-08-09 2016-01-27 株式会社ゼスト 業務割当装置及び業務割当プログラム
JP6439802B2 (ja) * 2014-12-08 2018-12-19 株式会社リコー 光偏向器、画像表示装置及び物体装置
JP5809382B1 (ja) * 2014-12-10 2015-11-10 楽天株式会社 サーバ、表示制御方法、および表示制御プログラム
US20220164739A1 (en) * 2015-03-05 2022-05-26 Quitchet,LLC Real-time scheduling and synchronization of real estate transactions
JP6551198B2 (ja) * 2015-11-30 2019-07-31 富士通株式会社 元素識別装置、元素識別プログラムおよび元素識別方法
JP6904534B2 (ja) * 2017-02-10 2021-07-21 株式会社リコー 情報処理装置、情報処理システム、移動経路決定方法及びプログラム
JP7194147B2 (ja) * 2020-04-16 2022-12-21 株式会社豊田中央研究所 工程設計の支援装置、支援方法および支援プログラム
JP7268719B1 (ja) 2021-11-22 2023-05-08 フジテック株式会社 出向計画システム、制御方法およびプログラム
JP7298666B2 (ja) * 2021-11-22 2023-06-27 フジテック株式会社 出向計画システム、制御方法およびプログラム
JP7633570B2 (ja) * 2021-12-01 2025-02-20 富士通株式会社 情報処理装置、立案方法、および立案プログラム
JP7518310B1 (ja) * 2024-03-19 2024-07-17 株式会社 日立産業制御ソリューションズ 巡回支援装置、巡回支援プログラム、および、巡回支援方法

Family Cites Families (35)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5272638A (en) * 1991-05-31 1993-12-21 Texas Instruments Incorporated Systems and methods for planning the scheduling travel routes
US5799263A (en) * 1996-04-15 1998-08-25 Bct Systems Public transit system and apparatus and method for dispatching public transit vehicles
JP3347006B2 (ja) * 1996-12-19 2002-11-20 日立エンジニアリング株式会社 計画立案装置および計画立案方法
US6754634B1 (en) * 1998-04-01 2004-06-22 William P. C. Ho Method for scheduling transportation resources
US6453298B2 (en) * 1998-07-10 2002-09-17 Honda Giken Kogyo Kabushiki Kaisha Method of operating a vehicle redistribution system based upon predicted ride demands
JP3900394B2 (ja) * 1998-10-22 2007-04-04 本田技研工業株式会社 配車システム
US6411897B1 (en) * 2000-07-10 2002-06-25 Iap Intermodal, Llc Method to schedule a vehicle in real-time to transport freight and passengers
US6356838B1 (en) * 2000-07-25 2002-03-12 Sunil Paul System and method for determining an efficient transportation route
KR20000063909A (ko) * 2000-08-10 2000-11-06 기준성 통신망을 이용한 운송정보 처리시스템과 그 방법
JP2002154612A (ja) * 2000-11-15 2002-05-28 Internatl Business Mach Corp <Ibm> 経路探索システム及び経路探索方法
JP2002215219A (ja) * 2001-01-23 2002-07-31 Mitsubishi Heavy Ind Ltd スケジューリング評価装置およびスケジューリング評価方法
US6904421B2 (en) * 2001-04-26 2005-06-07 Honeywell International Inc. Methods for solving the traveling salesman problem
GB2381884A (en) * 2001-07-16 2003-05-14 Pablo D Cappellini A search engine of flexibly-defined paths applicable to the search of transportation-related routes
US6980885B2 (en) * 2001-09-24 2005-12-27 I2 Technologies Us, Inc. Routing shipments according to criticality
US20030135304A1 (en) * 2002-01-11 2003-07-17 Brian Sroub System and method for managing transportation assets
US7363126B1 (en) * 2002-08-22 2008-04-22 United Parcel Service Of America Core area territory planning for optimizing driver familiarity and route flexibility
US7840434B2 (en) * 2002-10-29 2010-11-23 At&T Intellectual Property I, L. P. Methods and systems for assigning multiple tasks
US20040107110A1 (en) * 2002-12-02 2004-06-03 Jens Gottlieb Optimization of transport with multiple vehicles
US7627535B2 (en) * 2002-12-13 2009-12-01 Newspaper Delivery Technologies, Inc. Method and apparatus for supporting delivery, sale and billing of perishable and time-sensitive goods such as newspapers, periodicals and direct marketing and promotional materials
US20040133411A1 (en) * 2003-01-08 2004-07-08 Derrick Babb Automated Transit System
US20040225544A1 (en) * 2003-05-06 2004-11-11 Dorothy Camer Method, apparatus, and program for efficiently deploying vehicles to meet the mobility needs of a densely populated urban area
US20050216182A1 (en) * 2004-03-24 2005-09-29 Hussain Talib S Vehicle routing and path planning
GB0420097D0 (en) * 2004-09-10 2004-10-13 Cotares Ltd Apparatus for and method of providing data to an external application
US20060161335A1 (en) * 2005-01-14 2006-07-20 Ross Beinhaker Routing system and method
US7624024B2 (en) * 2005-04-18 2009-11-24 United Parcel Service Of America, Inc. Systems and methods for dynamically updating a dispatch plan
CA2554651A1 (en) * 2006-07-31 2008-01-31 Trapeze Software Inc. System and method for optimizing a transit network
US20080077464A1 (en) * 2006-09-22 2008-03-27 Sap Ag Vehicle scheduling and routing with trailers
EP2135200A4 (en) * 2007-02-12 2011-12-28 Sean O'sullivan Shared transport system and service network
US8893130B2 (en) * 2007-03-26 2014-11-18 Raytheon Company Task scheduling method and system
JP2009009312A (ja) * 2007-06-27 2009-01-15 Jfe Steel Kk 生産計画作成支援装置、生産計画作成支援方法および生産計画作成支援プログラム
EP2179385A2 (en) * 2007-07-09 2010-04-28 Technion Research & Development Foundation Ltd. Routing methods for multiple geographical entities
US20090048890A1 (en) * 2007-08-16 2009-02-19 Burgh Stuart G Delivery Management System for Quick Service Restaurants
US8082095B2 (en) * 2008-09-12 2011-12-20 General Motors Llc Enhanced passenger pickup via telematics synchronization
US8886453B2 (en) * 2008-12-11 2014-11-11 Telogis, Inc. System and method for efficient routing on a network in the presence of multiple-edge restrictions and other constraints
US9727829B2 (en) * 2009-11-25 2017-08-08 General Electric Company Systems and methods for multi-resource scheduling

Also Published As

Publication number Publication date
JP2013025509A (ja) 2013-02-04
US20130024227A1 (en) 2013-01-24

Similar Documents

Publication Publication Date Title
JP5772332B2 (ja) 巡回路決定についてのプログラム、方法及び装置
US10655975B2 (en) System and method for routing optimization
Gaspero et al. Balancing bike sharing systems with constraint programming
Lu et al. Robust scheduling on a single machine to minimize total flow time
Ye et al. A genetic algorithm for job-shop scheduling
Anagnostopoulos et al. Resource-constrained critical path scheduling by a GRASP-based hyperheuristic
CN105157712A (zh) 一种车辆路径的规划方法和规划系统
CN118502354B (zh) 一种数控加工生产线排程方法、装置、设备及存储介质
Rabet et al. A hybrid metaheuristic and simulation approach towards green project scheduling
Tang et al. Dual bounds from decision diagram-based route relaxations: An application to truck-drone routing
CN109255462B (zh) 一种货物配送方法及装置
CN107944748B (zh) 柔性作业车间人员配置及作业排序方法
Hu et al. The bus sightseeing problem
Kowalczyk et al. A flow-based formulation for parallel machine scheduling using decision diagrams
Holliday et al. Augmenting transit network design algorithms with deep learning
Bahalke et al. Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs
Montiel et al. Combinatorial complexity problem reduction by the use of artificial vaccines
Costa et al. In-route task selection in spatial crowdsourcing
CN109377111A (zh) 基于改进模拟退火算法的作业调度方法和装置
Karbowska-Chilinska et al. Maximization of attractiveness EV tourist routes
CN114169488B (zh) 基于混合元启发式算法的带容量约束的车辆路径获取方法
US20240054412A1 (en) Method and system for generating vehicle routes
CN117273590A (zh) 一种求解车辆路径优化问题的神经组合优化方法及系统
Argon et al. Optimal control of a single server in a finite-population queueing network
Liao et al. Reinforcement learning for routing

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20140404

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20150219

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20150224

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20150424

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20150602

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20150615

R150 Certificate of patent or registration of utility model

Ref document number: 5772332

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

LAPS Cancellation because of no payment of annual fees