車輛運用計劃編制裝置以及方法

2023-05-09 01:49:51

專利名稱：：車輛運用計劃編制裝置以及方法
技術領域：
：本發明涉及一種車輛運用計劃編制裝置以及方法，其考慮運用限定約束對能使用的多臺車輛分配全部多種運用，該運用確定了出發時刻、出發地點、到達時刻、到達地點，尤其涉及滿足車輛運用計劃的約束的初期方案的編制。
背景技術：
：在眾多鐵道從業人員中，根據列車運用計劃，關於在圖表(列車運行圖表)中所劃出的表示列車運行的斜線即列車線(trainline)，確定了從始發站到終點站之間的發車到達時刻，但實際上為了進行列車運用，必須決定對這些列車所分配的鐵道車輛編組(以下，稱為"車輛，，)。將確定該車輛的分配稱為車輛運用。在考慮車輛運用的情況下，有時也按每條列車線考慮車輛的分配，有時也以線幾條相交連接的線組為單位，考慮車輛的分配。於是，將分配車輛的最小單位稱為"運用"，進行將這些運用無一遺漏地分配給任何一個車輛的作業。在各運用中，考慮運用限定約束，對能使用的多臺車輛無一遺漏地分配確定了出發時刻、出發地點、到達時刻、到達地點的該全部多項運用。但是，也可能會有在同一天對同一臺車輛分配能夠並存的多項運用的情況。在該車輛運用中，根據「鉄道(D只^^工一i;乂歹7WrfyX、厶」(鉄道総合技術研究所運輸、>只於厶研究室著)，作為一般的約束，有以下這些。(l)各臺車輛，第二天只能從前一天的最終到達地點出發，還有在每天對同一臺車輛分配多項運用的情況下，第二項以後分配的運用，受從前一個到達地點出發的運用約束(以下，稱為"接續約束，，)。(2)根據各線路的設備條件的不同，限定可運用車輛形式。(3)關於每臺車輛的整體檢查、輪流檢查、動作檢查等的檢查，根據法令有義務定期實施。(4)必須定期確保車體、客室內的清掃、補給等的維護作業的時間。一般來說，每隔一定期間編制滿足這些約束的計劃方案的情況較多，將該作業稱為"原始計劃編制"。另外，在這種情況下，必須考慮到與前一個期間的連接，所以重新確定與計劃開始日相關的約束。另一方面，在由於列車運行圖表混亂等使得運用混亂時、或在緊急插入車輛的作業預定時等，必須變更原來的計劃，在這種情況下，多是一邊考慮緊急的情況一邊進行以儘可能早的天數重回原來的計劃的計劃變更。將該作業稱為"修正計劃編制"。該修正計劃編制時，在目標日之後必須進行原來的計劃預定，所以不但與計劃開始日相關的約束、還有與每臺車輛在目標日應該到達的位置相關的約束都另行確定。綜合該"原始計劃編制，，和"修正計劃編制"的作業，將其稱為車輛運用計劃編制。針對具有該複雜的約束的車輛運用計劃編制的問題，一直以來，多是在眾多的鐵道從業人員中選定計劃編制擔當者，基於擔當者自身的經驗和知識，以手動作業進行編制。一般來說，每隔一定的期間，進行編製圖6所示的車輛運用表的原始計劃編制，還有一邊進行該計劃的適當變更一邊進行修正計劃編制。公開了幾項自動編制該車輛運用計劃編制的技術。例如，有這樣一種技術，即通過以列車線為節點，以列車線的連接可能性為弧線的圖表(且將不同日期的同一列車視為同一節點)，將車輛運用計劃編制問題模式化，通過得到該圖表上的巡迴路，周期性地自動編制車輛運用計劃方案。另外，還有一種技術，即通過以運用為節點、以運用的連接可能性為弧線的圖表將車輛運用計劃編制問題模式化，使用該圖表上的遺傳算法，從而自動編制進一步提高評價值的那樣的計劃方案。而且，也公開了這樣一種技術，關於車輛運用計劃編制問題，最初編制周期性的輪流圖，根據需要適當變更該圖，從而自動編制計劃方案(例如，參照專利文獻l)。專利文獻1:日本特開2000-71988號公報在計劃編制擔當者進行原始計劃編制或^^正計劃編制時，其編制順序是試行錯誤基礎，所以需要大量的時間，另外也存在計劃的品質依存於擔當者個人的能力之類的問題。另外，在進行修正計劃編制時，人們的作業並非一定充分，所以有時超過需要對預定進行變更的變更作業的超前(overhead)變大，有時因為無論有沒有解都不能夠發現解，所以不得不進行不停止而進行回送、運用替換或者車輛交換這樣的緊急手法。另一方面，在現有技術中，雖然能夠編制周期性的車輛運用計劃方案、或大致周期性的車輛運用計劃方案，但是不能夠與一般經常出現的情況相對應。原因在於，在實際的圖表中平日圖表和周末休息日圖表等並存，而且節日非周期性地出現，所以原本是非周期性的。另外，對車輛實施的檢查計劃、清掃計劃等的約束，關係到作業人員、作業場所的預定等，所以也難以變為周期性的。接著，在使用圖表上的遺傳的算法的手法中，在發現初期解之後，根據該初期解順次產生評價值更高的解，但有時發現初期解本身就是很困難的，能夠求解的限於約束寬鬆的單純的問題。尤其是在本發明作為對象的那樣的有在現實中經常出現的約束的問題中，得到初期解本身就是很大的難題，該問題出現在存在與在目標日應該到達的位置相關的約束時、運用限定約束的約束嚴格時、在同一天對同一臺車輛分配多項運用時等。進而，在專利文獻l的編制周期性的輪流圖的技術中，在初期解的探索階段或者用於編制更好的計劃的計劃變更階段中，成為不滿足約束的計劃時，通過追溯(backtrack)探索對滿足約束的解進行探索。但是，該方法，只能探索不滿足約束的車輛和其他車輛之間的交換一次的解，以這樣單純的方法能夠得到滿足約束的解，這只限於約束寬鬆單純的情況。實際上，在該方法中，對於本發明的以下的實施方式所述的任合問題都不能夠得到解。另外，在增加如專利文獻l所述的那樣的約束時，增加追溯的檢索條件這樣的作法並不優選。原因在於，在實際問題那樣的約束每天變化的狀態下，追溯探索部的維護成本增加，運用變得困難。根據以上的現有技術，可以預料針對具有嚴格約束的車輛運用計劃，很難得到滿足約束的解。
發明內容本發明是考慮上述事項而做出的，其的目的在於，提供一種能夠以更短時間自動編制滿足給定約束的車輛運用表的車輛運用計劃編制裝置以及方法。為了解決上述的問題，本發明的車輛運用計劃編制裝置，其特徵在於，具備編制單元，其編制運用連接圖表，在該運用連接圖表中，在從開始日到目標日的期間，對每臺車輛，分別用節點表示開始日地點、由出發時刻、出發地點、到達時刻和到達地點所確定的運用、以及目標日地點，根據地點和時刻將可以連接的節點全部用弧線連接；設定單元，其在從開始日起順次到目標日為止的每天，對每臺車輛，分配用所述弧線連接的所述運用，設定一條連結連接的所述運用的線路；交換單元，其在有車輛在目標日不在目標日地點時，為了使全部的車輛在目標日都在目標日地點，在換；和輸出單元，其在發現全部車輛在目標日在目標日地點的多條線路時，將與該線路相對應的運用的分配作為車輛運用計劃輸出。根據本發明的車輛運用計劃編制裝置以及方法，能夠以短時間自動編制滿足給定約束的車輛運用表。圖l是表示本實施方式的車輛運用計劃編制裝置的基本結構的圖。圖2是表示成為圖1的車輛運用計劃自動編制部的輸入的開始日信息以及目標日信息的一例的圖。圖3是表示成為圖1的車輛運用計劃自動編制部的輸入的車輛信息的一例的圖。圖4是表示成為圖1的車輛運用計劃自動編制部的輸入的運用圖信息的一例的圖。圖5是表示成為圖1的車輛運用計劃自動編制部的輸入的運用限定約束信息的一例的圖。圖6是表示包括成為圖1的車輛運用計劃自動編制部的輸出的計劃候補方案的車輛運用表的一例的圖。圖7是表示運用連接圖表的一例的圖。圖8是表示分配圖表的一例的圖。圖9是第一以及第二實施方式的車輛運用計劃編制裝置的框圖。圖IO是表示圖9的車輛運用計劃編制裝置的動作的一例的流程圖。圖ll是表示圖9的運用連接圖表編制部的動作的一例的流程圖。圖12是表示對各臺車輛分配第零日節點的一例的圖。圖13是圖9的貪婪(greedy)分配部的動作的一例的流程圖。圖14是表示第一天的貪婪分配的一例的圖。圖15是表示由圖9的貪婪分配部所實現的預備節點分配的一例的圖。圖16是表示第二天對車輛2的預備節點分配的一例的圖。圖17是表示圖9的追溯(backtrack)探索部的動作的一例的流程圖。圖18是表示第一實施方式的適用例的圖。圖19是表示發現以圖18的車輛1為起點的線路pi的情況的圖。圖20是表示基於圖19的線路p進行交換的情況的圖。圖21是表示發現以圖18的車輛1為起點的線路p2的情況的圖。圖22是表示基於圖21的線路p2進行交換的情況的圖。圖23是表示第二實施方式中的圖9的追溯探索部的動作的一例的流程圖。圖24是表示第二實施方式的適用例的圖。圖25是表示發現以圖24的車輛1為起點的線路p3的情況的圖。圖26是表示基於圖25的線路p3進行交換的情況的圖。圖27是表示以圖24的車輛1為起點遞歸執行追溯探索的情況的圖。圖28是表示基於圖27的線路p4進行交換的情況的圖。圖29是第三實施方式的車輛運用計劃編制裝置的框圖。圖30是表示第三實施方式中的圖9的追溯探索部的動作的一例的流程圖31是表示第三實施方式的適用例的圖。圖32是表示發現以圖31的車輛1為起點的線路ps的情況的圖圖33是表示基於圖32的線路ps進行交換的情況的圖。圖34是用於說明預備車輛減少一臺的分配的實現的圖。符號說明101:103:112:114:121123:125:902:904:906:908:910:912:車輛運用計劃自動編制部102:輸入處理裝置tableseeoriginaldocumentpage10運用限定約束信息901:開始日信息存儲部目標日信息存儲部903:車輛信息存儲部運用圖信息存儲部卯5:運用連接圖表編制部運用連接圖表存儲部907追溯探索部909計劃候補方案存儲部911貪婪分配部計劃候補方案存儲部失敗信號存儲部車輛運用表存儲部2卯1:運用限定約束信息存儲部具體實施例方式以下，一邊參照附圖一邊詳細說明本發明的實施方式所涉及的車輛運行計劃編制裝置以及方法。另外，在以下的實施方式中，關於標註同一附圖標記的部分，作為進行同樣動作的部分省略重複的說明。在本實施方式中，以節點和弧線所示的運用連接圖表使車輛運用計劃編制的問題模式化。節點表示運用，弧線表示運用之間的連接可能性。各車輛的一連串的分配作為該運用連接圖表上的一條線路進行表示。在該運用連接圖表上，通過反覆執行後述的貪婪(greedy)分配部和後述的追溯探索部，從而進行車輛運用計劃自動編制，其中，追溯探索部在計劃編制的中途階段貪婪分配發生擁堵時列舉打開擁堵的候補。尤其，在本實施方式中，其特徵在於，在追溯探索部消除擁堵時，以運用連接圖表上的已計劃弧線為基準，根據交換次數較少、更加單純的變更方案包羅地列舉出解。(系統的基本結構)參照圖l說明車輛運用計劃編制裝置的基本結構。本實施方式的車輛運用計劃編制裝置，包括車輛運用計劃自動編制部101、輸入處理裝置102和輸出處理裝置103。輸入處理裝置102,接受各種數據輸入，將它們變換為包括開始日信息121、目標日信息122、車輛信息122、運用圖信息124以及運用限定約束信息125的輸入數據105。車輛運用計劃自動編制部101，輸入開始日信息121、目標日信息122、車輛信息123、運用圖信息124和運用限定約束信息125，進行預定的演算，輸出計劃候補方案112或者失敗信號115。輸出處理裝置103,輸入計劃候補方案112或者失敗信號115,對它們施以簡單加工，輸出車輛運用表114。其中，關於輸入處理裝置102以及輸出處理裝置103的詳細情況，在本發明中沒有特別限定，因此，以下主要對車輛運用計劃自動編制部101的詳細情況進行說明。(開始日信息121以及目標日信息122)接著，參照圖2對成為車輛運用計劃自動編制部101的輸入的開始日信息121以及目標日信息122進行說明。開始日信息121，如圖2所示，關於原始計劃編制或者修正計劃編制ii的各項，表示編制計劃預定的期間中的開始日的日期。目標日信息122，如圖2所示，關於原始計劃編制或者修正計劃編制的各項，表示編制計劃預定的期間的目標日的日期。(車輛信息123)接著，參照圖3，對成為車輛運用計劃自動編制部101的輸入的車輛信息123進行說明。該車輛信息123，如圖3所示，具有每臺車輛的計劃開始日的地點以及修正計劃編制時的目標到達地點的信息。(運用圖信息124)接著，參照圖4對成為車輛運用計劃自動編制部101的輸入的運用圖信息124進行說明。運用圖信息124，如圖4所示，對才艮據每天的圖表確定的在該日應該分配的運用的圖進行定義。例如，在平日圖表與休息日圖表不同的情況下，一般來說該運用圖也不同。該運用圖信息124，按每個圖包括多個運用。(運用數據)接著，對構成運用圖信息124的運用數據的詳細情況進行說明。對運用數據而言，如圖4所示，具有出發地點、出發時刻、到達地點、到達時刻這四個屬性。以下，為了模式地表示該情況，像圖18的上圖那樣以區段(block)表示運用，該區段順次配置在縱向表示車輛、橫向表示日期以及時刻的表中，從而表示對運用車輛的分配。如該圖18所示，對同一車輛的分配，排在一橫列，因此運用之間的接續約束，從在開始日分配的運用起順序橫向來看，能夠確認。即，分配給同一車輛的前後的運用，必須是前次運用的到達地點與下次運用的出發地點一致、而且前次運用的到達時間在下次運用的出發時間之前。另外，在修正計劃編制時，必須根據車輛信息123在目標日到達確定的地點。將其稱為"目標日約束"。(運用限定約束信息125)接著，參照圖5對成為車輛運用自動計劃部101的輸入的運用限定約束信息125進行說明。運用限定約束信息125，如圖5所示，是對某日某臺車輛限定可分配的運用的信息。例如在第一天對車輛1實施法定檢查、清掃等時，在有不能與該作業實施並行的運用的情況下，就會有"在第一天不能對車輛1分配運用57"這樣的約束。另外，由於運用的特殊事項(車輛的臺數、保安裝置的約束等)，而限定分配運用的車輛時，就會有"車輛4通常只能分配運用23"這樣的約束。而且，在某臺車輛在一定期間進入工廠時，出現在一定期間無法分配運行的狀況，就會有"車輛6從第二天到第十天不能分配運用，，這樣的約束。(車輛運用計劃自動編制部101的輸出)接著，參照圖6對車輛運用計劃自動編制部101的輸出數據104進行說明。車輛運用計劃自動編制部101，在車輛運用計劃編製成功時輸出計劃候補方案。該計劃候補方案是成為圖6的車輛運用表114的基礎的數據。另一方面，車輛運用計劃自動編制部101，在車輛運用計劃編制失敗時輸出失敗信號115。(運用連接圖表113)接著，參照圖7對在以下的實施方式中所用的運用連接圖表113進行說明。運用連接圖表113，如圖7所示，是將構成各日的運用圖的各運用作為節點，以有方向性的弧線連接該運用之間的連接可能性的圖表。另外，僅將實際存在的運用作為節點，例如第一天到達地點A的運用節點，能夠與第二天以後從地點A出發的全部的運用節點連接，因此變得繁雜。於是，在每日準備被稱為"預備節點"的表示滯留在與第一日相同的地點的情況的節點，對於一天也沒有分配一個運用的節點，分配該預備節點。這裡滯留在A處的預備節點表示終日滯留在同一地點A處的預備車輛，所以將其屬性設定如下。出發地點A達到地點A出發時刻非常早的時刻到達時刻非常晚的時刻通過這樣設定預備節點的屬性，以下，能夠無區別地處理該預備節點和根據其他基礎的某一運用節點，而且能夠實現對於分配了預備節點的車輛不分配其他運用這樣的約束。另外，通過導入該預備節點，會有這樣的效果，即與下一個節點之間的連接可能性只要考慮當天以及翌日就足夠了。進而，在運用連接圖表113中，為了簡化說明，如圖7所示，對每臺車輛追加與開始日出發地點相當的節點(以下，稱為"第零日節點")，關於在與開始日的各運用相當的節點中存在出發地點與第零日節點的地點一致的節點的情況，通過有方向性的弧線連接第零日節點和該節點。(車輛運用計劃編制的問題設定)在通過該運用連接圖表113模式化時，關於各臺車輛，在存在從第零日節點起滿足接續約束的線路、且各臺車輛的線路所含的節點沒有重複且預備節點以外的節點全部必須包含於某一車輛的線路的情況下，與該線路相當的計劃，變成如圖8所示的滿足接續約束的計劃候補方案111。圖8表示到第二日為止的分配的例子，在圖8的圖表中以實線表示接續分配給各臺車輛的運用節點的線路。以下，將運用連接圖表113上的可以連接的弧線中的該實線上的弧線稱為"已計劃弧線，，，將通過該已計劃弧線表示已分配的運用的接續的運用連接圖表113稱為"分配圖表"。以下的貪婪分配、追溯探索與該分配圖表的更新同時進行。在圖8所示的情況下，的確從各臺車輛的第零日節點開始的線路，滿足接續約束且第一日和第二日的預備節點以外的節點全部被分配給任意的車輛，因此成為滿足接續約束的計劃候補方案111。滿足該接續約束的計劃候補方案111，通過輸出處理裝置103變換為圖6所示的車輛運用表114。(第一實施方式)在本實施方式中，對不考慮運用限定約束信息125時的修正計劃編制的情況進行說明。另外，在原始計劃編制時，在以下的處理中視為沒有目標日約束即可。參照圖9對本實施方式的車輛運用計劃編制裝置進行說明。本實施方式的車輛運用計劃編制裝置，包括輸入處理裝置102、開始曰信息存儲部901、目標日信息存儲部卯l、車輛信息存儲部903、運用圖信息(運用數據)存儲部904、運用連接圖表編制部卯5、運用連接圖表存儲部卯6、貪婪分配部卯7、追溯探索部908、滿足接續約束的計劃候補方案(分配圖表)存儲部909、計劃候補方案(分配圖表)存儲部910、失敗信號存儲部911、輸出處理裝置103和車輛運用表存儲部912。車輛運用計劃自動編制部IOI,包括運用連接圖表編制部905、運用連接圖表存儲部卯6、貪婪分配部卯7、追溯探索部908、滿足接續約束的計劃候補方案909和計劃候補方案存儲部910。車輛運用計劃自動編制部101，輸入開始日信息存儲部卯l中所存儲的開始日信息121、目標日信息存儲部卯2中所存儲的目標日信息122、車輛信息存儲部卯3中所存儲的車輛信息123和運用圖信息存儲部卯4中所存儲的運用圖信息124，在計劃失敗時輸出失敗信號，在計劃成功時輸出計劃候補方案112。運用連接圖表編制部905編制運用連接圖表113。參照圖ll對其詳細情況進行說明。貪婪分配部907，為了滿足接續約束，將第m(m為自然數)天圖所含的各運用節點全部分配給任意的車輛。關於其詳情，在後文中參照圖13進行說明。貪婪分配部907，對在第m日一個運用節點也沒有分配的車輛，分配滯留在該車輛的前一天的到達地點的預備節點。關於其詳情，在後文中參照圖15進行說明。追溯探索部卯8，在存在沒有滿足目標日約束的車輛h的情況下，關於車輛h,進行追溯探索。關於該追溯探索，使交換閾值k從l順次增加至最大值(max)，同時直至追溯成功，重複執行。關於追溯探索的詳細情況，在後文中參照圖17進行說明。另外，在修正計劃編製成功時，沒有輸入目標日信息122而使目標日15信息122從1起順次增加，同時能夠進行儘早恢復原樣的計劃的擴張。在這種情況下，針對目標日的候補日必須全部具有車輛信息123的各車輛的目標到達地點的信息。(第一實施方式的控制流程)接著，參照圖IO對第一實施方式所涉及的車輛運用計劃編制裝置的動作的一例進行說明。這裡，考慮修正計劃編制的目標日為第n(n為自然數)日的情況。另夕卜，該圖10的流程，成為與以下的第二實施方式以及第三實施方式中通用的流程。但是，在第三實施方式中，在分歧步驟S1005中不僅對目標日約束也對運用限定約束進行檢查，這一點不同。首先，在步驟l中，進行運用連接圖表113的編制(步驟S1001)。接著，重複從開始日到目標日的各日(第m日)，從m=l(步驟S1002)到n^n為止的步驟S1003到步驟S1010的循環l。在步驟2、步驟3、步驟4中，在從開始日到目標日的各日(第m日)中，通過貪婪分配部卯7以及追溯探索部908，邊更新分配圖表邊進行滿足約束的計劃編制。在步驟2中，貪婪分配部907，為了滿足接續約束，將第m日圖所含的各運用節點全部分配給任意的車輛h(步驟S1003)。接著，在步驟3中，貪婪分配部卯7，對在第m日一個運用也沒有分配的車輛分配滯留在該車輛的前一天的到達地點的預備節點(步驟S1004)。在該時間點，在沒有不滿足目標日約束的車輛h時(步驟S1005的否)，在m為目標日(m=n)時跳出循環1並結束，在m不是目標日時m增加1而進入翌日。另外，在貪婪分配以及追溯探索完成的狀態即步驟S1005的時間點，必須成為滿足接續約束的分配，所以全部的車輛滿足目標日約束的分配成為滿足全部約束的分配。另外，目標日約束，在目標日前一天(m=n-l)以外不進行檢查，所以實際上在步驟S1005中為是的情況，也僅限於m=n-l的情況。另一方面，在存在不滿足目標日約束的車輛h時(步驟S1005的是)，關於車輛h，重複執行交換闊值K=l(步驟S1006)到K=max為止的步驟S1007至步驟S1009的循環2。在步驟4中，通過追溯探索部卯8進行追溯探索。關於該追溯探索，交換閾值K從l順次增加至max，同時反覆執行直到追溯探索成功。在追索探索成功(步驟S1008的是)時，再次進行步驟S1005，即便K-max在追索探索沒有成功時，輸出失敗信號並結束(S1012)。通過以上的處理，在直到目標日為止的全部的分配成功時，輸出車輛運用計劃表並結束。另外，關於圖10的流程，即便在有以下列舉的各項變化的情況下也得到同樣的效果。首先，在圖10的步驟2中，設為一天量的運用全部首先通過貪婪分配進行分配，而後進行追索探索的流程，但也可以是逐個運用反覆進行貪婪分配和追索探索那樣的流程。另外，在圖10的步驟3中，設為對在該日一個運用節點也沒有分配的車輛分配預備節點的流程，但也可以不通過預備節點表示在某一地點的終日滯留，而通過變更運用連接圖表的由有方向性的弧線所連接的條件來表示。進而，在圖10的步驟4的追溯探索中，事先確定最大交換閾值kmax，同時進行順次增加閾值K，但也可以是從最初將最大交換閾值kmax設為閾值進行追溯探索的流程。(運用連接圖表編制部905)接著，參照圖11對運用連接圖表編制部905編制運用連接圖表113的動作的一例進行說明。首先，對各車輛分配第零天節點(步驟S1101)。關於第零天節點的分配的例子，使用圖12進行說明。車輛信息123如圖3所示，車輛1的開始曰地點為A，所以作為第零天節點，分配A節點。該節點，能夠與在第一天以地點A為出發地點的運用相連接。同樣，對車輛2分配B節點，對車輛3分配B節點(參照圖7)。接著，每天順次執行步驟l以及步驟2，以編制節點。即，將m設定為1，直到m=n，重複步驟S1103至步驟S1105的循環1,接著，重複步驟S1106的循環2。在步驟l中，追加與第m天圖所含的運用相當的節點，在步驟2中追加第m天所必須的預備節點。另外，該預備節點，根據每個地點編制出有可能的最大數量以上的數量。作為第一天以及第二天的運用圖，假定圖4，則如圖7所示，作為第一天節點，追加89、41、79、83、43以及57的各運用節點，作為第二天節點，追加39以及53的運用節點。另外，對於各天，追加每個地點的預備節點(此時分別逐個以A預備、B預備表示)。接著，按順序探索所述編制的各節點p，對能夠連接的節點p，以有方向性的弧線連接(步驟S1106)。這裡，能夠與節點p連接的條件是節點q是與節點p同一天或翌日的節點，節點p的到達地點與節點q的出發地點一致，而且節點p的到達時刻比節點q的出發時刻早。在圖7的例子中，基於與各節點相當的運用的出發時刻、出發地點、到達時刻、到達地點，能夠連接的節點之間以弧線相連即可。(貪婪分配部907)接著，參照圖13對貪婪分配部卯7的動作的一例進行說明。貪婪分配，將第m天的運用圖所含的各運用按出發時刻從早到晚的順序分配至滿足接續約束的可分配的車輛。例如，在圖14的例子中，按出發時刻從早到晚的順序以89—41—79這樣的順序進行分配。另外，在圖13的流程中，判定是否存在第m天的未分配運用(步驟S1301),在存在未分配運用的情況下，將第m天的運用圖所含的各運用按出發時刻從早到晚的順序分配至可分配的車輛(步驟S1302)，但這是用於將全部的運用可可靠地分配的方法之一。由此，只要是分配全部的運用的方法，並不特別限定於該順序。(確保最大P艮度預備車輛的貪婪分配部的動作的例子)這裡能夠分配的車輛是多臺，且其中包括當天的運用已經分配的車輛和當天的運用尚未分配的車輛，此時，可以設定優選對前者的已經分配的車輛進行分配這樣的基準。例如，在圖14的例子中分配79運用之後，在79運用之後考慮出發時刻較早的83運用的分配對象。作為該83運用的分配對象，作為滿足接續約束的，存在車輛l、車輛3以及車輛4的三種可能性(車輛2，由於41運用的到達時刻比83運用的出發時刻晚，所以不能分配)。這裡，當採用上述的基準時，將其分配至已經分配了運用的車輛1、車輛3以及還沒有分配運用的車輛4這三種可能性中的已經分配了運用的車輛1、車輛3中的任意一臺。當設定這樣的基準時，在貪婪分配結束之後得到的分配成為最大限度確保預備車輛的分配。在實際的車輛運用計劃中，以備不測情況儘可能地確保預備車輛是很重要的，因此用到這樣的基準的情況很多。(預備節點分配)接著，參照圖15對貪婪分配部907所進行的預備節點分配進行說明。預備節點的分配，判定在第m天的運用分配之後是否存在未分配運用的車輛(步驟S1501)，對一個運用也沒有分配的車輛分別分配滯留在前一天的最終到達地點的預備節點(步驟S1502)。在圖16的例子中，在第二天的運用全部(39、53)由貪婪分配分配之後，對車輛2還沒有分配一個運用，因此對車輛2分配預備節點(A預備)。在這樣的情況下，車輛2的第一天的最終到達地點是A,所以分配地點A的預備節點。(追溯探索)接著，參照圖17,對追索探索部908所進行的、車輛h不滿足約束時的交換次數為k次時直到第m天為止的追溯探索的詳細情況進行說明。(循環l整個線路的列舉)首先，在圖17的追溯探索中，通過最初的循環l，按順序尋找以車輛h的第零天節點為起點、滿足接續約束的全部線路中的、交換次數在k次以下的(但是，該線路是不包括非已計劃的預備節點的線路)。這裡，所謂交換次數是指，在分配圖表上，該線路通過非已計劃弧線的弧線(以下，稱為"交換弧線")的次數。在運用連接圖表上求出從車輛的第零天到第m天的全部滿足接續約束以及目標日約束的交換次數k次以下的線路p，重複步驟S1701到步驟S1703，直到找到全部的線路為止。首先，進行與線路p相對應的全部交換(步驟S1701)，判定位於線路p上的全部車輛是否滿足接續約束以及目標日約束(步驟S1702)。在滿足這些約束時，追溯成功處理結束(步19驟S1705)。當在步驟S1702中不滿足這些約束時，將在步驟S1701中所進行的交換恢復原樣(步驟S1703),以新的交換次數進行步驟S1701。具體而言，例如在圖8的分配圖表中，在以車輛1為起點滿足接續約束以及目標日約束的線路中，有p屍A—89—43—A預備、p屍A—89—57—A預備等。在線路p,中，弧線89—43是交換弧線，所以p,是交換次數為l的線路。另外，在線路p2中，弧線89—57以及57—A預備是交換弧線，所以P2是交換次數為2的線路。這裡，全部列舉交換次數在k次以內的線路的問題，成為對已分配弧線附加重疊O、對其以外的交換弧線附加重疊1，在分配圖表上列舉全部距離k以內的線路的問題。作為列舉全部距離k以內的線路的方法，已知深度優先法、寬度優先法、最好優先法等各種方法，使用其中的任意一種即可。(步驟l交換的執行)在通過上述的處理得到以車輛h的第零天節點為起點、交換次數k次以內的滿足接續約束的線路p時，全部進行與線路p的交換弧線相對應的交換(步驟S1701)。這裡所謂交換，意味著車輛h與分配了交換弧線的目標節點的車輛h2的全部置換該交換弧線節點以後的線路。例如，在圖8的線路p產A—89—43—A預備的情況下，基於交換弧線89—43的車輛1的交換後的線路變為A—89—43—A預備。另一方面，分配了交換弧線的目標節點43的車輛2的交換後的線路是(利用原來的車輛2的線路上的運用3的前一個節點41和原來的車輛1的線路上的運用89的後一個運用83)B—41—83—53。該分配圖表實際上不滿足接續約束，但在此時沒有進行檢查。另外，在像線路P2那樣包括多個交換弧線的情況下，從與線路上第零天節點靠近的交換弧線相當的交換起按順序執行交換。(約束檢查)在該步驟l的交換之後，進行被交換的全部車輛的接續約束以及目標日約束的檢查，假如在滿足任何一個約束的情況下(步驟S1702的是)，能夠編制滿足車輛h以及相關的全部車輛的約束的分配圖表，因此，追溯成功並結束。另一方面，在沒有滿足任何約束的情況下(步驟s1702的否)，與該線路p相對應的交換恢復原樣(步驟S1703)，進入下一個線路候補。(第一實施方式的具體例)以上所說明的第一實施方式的應用例以開始日=1、目標日=2、最大交換閾值kmax-2的追溯探索為中心，通過具體例來說明。另外，在圖18以後的附圖中，上部圖示運用區段分配的圖，下部圖示分配圖表。首先，按照圖10的流程，進行直到第二天的貪婪分配，得到圖18所示那樣的分配圖表(第一天是更加單純的處理所以省略說明)。此時，車輛1不滿足目標日約束(步驟S1005的是)，所以車輛h-l，進入追溯探索的流程(圖17)。最初在交換次數k=l時，首先，探索以車輛1的第零天節點即A節點為起點的距離1的線路，例如得到線路p屍A489—43—A預備(圖19)。這裡，線路Pl滿足接續約束也滿足車輛1的目標日約束，因此進入圖17的步驟l，執行基於該線路pi的交換，得到圖20那樣的分配圖表。接著，當檢查該分配圖表時，車輛2的運用41和運用83是不能連接的(因為不是可以連接的弧線)，所以不滿足接續約束(步驟S1702的否)。因此，基於線路pi的交換恢復原樣(圖17的步驟2)，進入下一個線路。之後，因為在交換次數l的線路中，不存在滿足接續約束以及目標日約束的線路，所以交換次數=2。在k=2時，探索以車輛1的第零天節點即A節點為起點的距離2的線路，例如得到線路p產A—89—57—A預備(圖21)。這裡，因為線路p2滿足接續約束和目標日約束，所以進入步驟S1701,執行基於該線路p2的交換，則得到圖22所示的分配圖表。接著，當對該分配圖表進行檢查時，因為車輛2和車輛3都滿足接續約束和目標日約束(步驟S1702的是)，所以追索成功。因此，跳出追溯探索的流程(圖17)，再次進入圖10的流程的圖10的步驟S1005，但這次因為全部的車輛都滿足目標日約束(步驟S1005的否)，所以不盡行追溯^:索。這裡，因為完成了直到目標日的計劃編制(m=n(=2))，所以跳出循環，計劃編制完成。根據以上說明的第一實施方式，為了滿足接續約束，每天對任意車輛分配該日期所包含的全部各種運用節點，對於不滿足目標日約束的車輛包羅地探索運用節點的組合，從而能夠在短時間內自動編制出車輛運用表，該車輛運用表滿足修正計劃編制問題的約束即滿足接續約束以及目標日約束。(第二實施方式)修正計劃的情況。本實施方式的車輛運用計劃編制裝置與第一實施方式的相同，只是動作多少不同。(第二實施方式的控制流程)首先，參照圖23對第二實施反方式所涉及的車輛運用計劃編制裝置的動作的一例進行說明。該第二實施方式的控制流程，除追溯探索的流程從圖17變為圖23這一點以外與第一實施方式的流程圖(圖IO)完全相同。因此，以下利用圖23的流程圖對第二實施方式的追溯探索的詳細情況進行說明。圖23的流程圖，與第一實施方式的圖17的流程圖相比較，不同點僅在於，在步驟S1701和步驟S1703之間插入步驟S2301、步驟S2302、步驟S2303。即，在第二實施方式中，在執行基於滿足約束的線路p(交換次數k')的交換之後，在存在不滿足接續約束或目標日約束的車輛h2且k>k，(步驟S2301的是)時，以該車輛h2為起點，再次以交換閾值作為k"(=k-k')執行(遞歸調用)該手續T2自身(步驟S2302),進行追溯是否成功的判定(步驟S2303)。這裡，車輛h是不滿足約束的車輛，因此滿足約束的線路p必需至少一次以上的交換，所以一定是k，〉0。因此，k，>k"(=k-k，)一定成立，因此每次遞歸調用交換閾值(k—k"...)都會減小。因此，遞歸調用的深度在最初調用手續T2時的交換閾值k以下，保證該手續T2必須停止。(第二實施方式的具體例)關於該第二實施方式的追溯探索，使用具體例進行說明。另外，設定為開始日=1、目標日=2、最大交換閾值kmax二2。首先，按照圖10的流程，進行直到第二天的貪婪分配，得到如圖24所示的分配圖表。在該分配圖表中，沒有滿足車輛1的目標日約束，所以設為h-l，進入追溯探索的流程(圖23)。另外，在下文中，在最初調用追溯探索T2時的交換閾值為k=l時追溯失敗之後，追溯探索T2的交換閾值變為k=2的狀況。在追溯探索中，首先探索以車輛l的第零曰節點即A節點為起點的距離2的線路，得到例如線路p3=A—89—A預備(交換次數k'=l)(圖25)。這裡，因為線路p3滿足接續約束和車輛1的目標日約束，所以進入圖23的步驟l,執行基於該線路p3的交換，則得到圖26所示那樣的分配圖表。接著，檢查該分配圖表，則不滿足車輛2的目標日約束(圖23的步驟S1702的否)且k>k，(2>l)(圖23的步驟S2301的是)，所以進入圖23的步驟3，這次遞歸地調用車輛h'(=2)的交換閾值k"(=2-1)即追溯探索T2(h，，k，，)。因此，這次進行將車輛h-2設為起點的交換閾值1的追溯探索。此時，得到例如圖27所示的線路p4=A—51—B預備(交換1次)。這裡，線路P4滿足接續約束和車輛1的目標日約束，因此進入圖23的步驟1，執行基於線路P4的交換，則得到圖28所示的分配圖表。接著，檢查該分配圖表，則車輛2和車輛3都滿足接續約束以及目標日約束，因此追溯成功。因此，跳出遞歸調用後的追溯探索的流程(圖23)，也跳出遞歸調用前的追溯探索的流程，再次進入步驟S1005,但這次因為全部車輛都滿足目標日約束(步驟S1005的否)，不進行追溯。這裡，因此完成了直到目標日為止的計劃編制(m=n(=2))，所以跳出循環，編制結束。根據以上說明的第二實施方式，能夠包羅地尋找交換次數在k次以內的解，因此能夠以高於第一實施方式的可能性在短時間內自動編制車輛運用表。(第三實施方式)本實施方式，如圖29的車輛運用計劃編制裝置的框圖所示，有時作為輸入車輛運用計劃自動編制部101的信息而追加圖1以及圖5所說明的運用限定約束信息125。本實施方式的車輛運用計劃編制裝置，在第一實施方式的車輛運用計劃編制裝置的裝置部分的基礎上還設有運用限定約束信息存儲部2901。其他的與第一實施方式相同。運用限定約束信息存儲部2901，存儲有運用限定約束信息125，對貪婪分配部卯7以及追溯探索部908提供該信息。運用限定約束信息125的信息，在運用限定約束的檢查時使用。(第三實施方式的控制流程)首先，參照圖30對第三實施方式所涉及的車輛運用計劃編制裝置的動作的一例進行說明。該第三實施方式的控制流程，在圖IO的流程圖的步驟S1005中不僅檢測目標日約束還檢測運用限定約束，以及追溯探索的流程從圖23變為圖30，除了這兩點以外與第二實施方式的流程圖完全相同。因此，以下利用圖30的流程圖對第三實施方式的追溯探索的詳細情況進行探索。圖30的流程圖中的與圖23的流程圖的不同點，僅在於在循環1以及步驟S3001中應該滿足的約束除了接續約束、目標日約束還有運用限定約束這一點。(第三實施方式的具體例)關於該第三實施方式的追溯探索，利用具體例進行說明。另外，設定開始日=1、目標日=2、最大交換閾值kmax-2。另夕卜，作為運用限定約束，存在車輛1在第一天不能分配57運用這樣的約束。首先，按照圖10的流程，進行直到第二天的貪婪分配，得到如圖31所示的分配圖表。在該分配圖表中，在第一天對車輛l分配運用57，這是不滿足運用限定約束的，所以設車輛h=l，進入追溯探索的流程(圖30)。另外，以下考慮交換次數h-l的探索後的狀況，設為k-2。在追溯探索中，首先，探索以車輛1的第零天節點即A節點為起點的距離2的線路，得到例如線路p5=A—89—43—A預備(交換次數k'=2)(圖32)。這裡，線路ps滿足接續約束和車輛1的目標日約束，因此進入圖30的步驟1，執行基於該線路ps的交換，則得到圖33所示的計劃。接著，如果檢查該分配圖表，車輛1、車輛2都滿足接續約束、目標曰約束和運用限定約束，所以追索成功。因此，跳出追溯探索的流程(圖23)，再次進入步驟S1005，這次全部車輛都滿足目標日約束(步驟S1005的否)，所以不進行追溯。這裡，因此完成了直到目標日的計劃(m=n(=2))，所以跳出循環編制結束。根據以上說明的第三實施方式，能夠在短時間內自動編制滿足修正計劃編制問題的約束即滿足運用限定約束的車輛運用表。(與預備節點相關的工作)另外，在從上述第一實施方式到第三實施方式的追溯探索中，將預備節點與通常的運用同樣看待，所以假設在上述貪婪分配中編制最大限度確保預備車輛的分配計劃時，即便在以後的追溯探索中也只能得到最大限度確保預備車輛的分配計劃。其結果是，例如不能實現如圖34的右上圖那樣預備車輛為l臺的較少的分配。一般來說，如上所述，多數情況下最大限度確保預備車輛是很重要的，但也有以與其他約束組合要編制不最大限度確保預備車輛的分配計劃的可能性。在這樣的情況下，事先如下給出與地點B相關的預備節點的各屬性的定義(上述的定義，與到達時刻的定義不同)。出發地點B到達地點B出發時刻非常早的時刻到達時刻非常早的時刻這樣設定，則在預備節點之後，能夠與在該日以地點B為出發地點的全部運用節點連接，因此能夠進行圖34的下圖那樣的交換，能夠得到預備車輛的數量不是最大數量(此時最大數量小於1臺)的分配計劃。根據以上所示的實施方式，為了滿足接續約束，每天對任意車輛分配該日期所含有的全部各運用節點，對不滿足目標日約束(以及運用限定約束)的車輛包羅地探索運用節點的組合，從而能夠在短時間內自動編制滿足給定的約束的車輛運用表。另外，在本發明中，具有能夠將由於能夠運用的車輛的限定約束、每臺車輛的檢查、清掃約束、進入工廠等所導致的車輛的不能使用約束等的各種複雜多樣的約束以一般化的運用限定約束的表述統一處理的特長。因此，在實際的運用中，即便在追加或變更約束時，沒有必要改變約束處理工具(engine)自身，只要改變運用限定約束的編制手法即可。因此，具有能夠降低維護成本的效果。另外，在以上的實施方式中，基本上有時也採用詳盡(thoroughly)基礎的探索方法，不存在用於控制探索方法自身的參數，具有每次適用對象線路或運用狀況變化，能夠降低參數調準的費用的效果。另外，本發明並不是原樣限定於上述實施方式的，在實施階段能夠在不脫離其要旨的範圍內變化構成要素具體化。另外，通過適當組合在上述實施方式中公開的多個構成要素，從而能夠形成各種發明。例如，可以從實施方式所公開的全部構成要素中去除幾個構成要素。進而，也可以是適當組合不同實施方式中的構成要素。2權利要求1.一種車輛運用計劃編制裝置，其特徵在於，具備編制單元，其編制運用連接圖表，在該運用連接圖表中，在從開始日到目標日的期間，對每臺車輛，分別用節點表示開始日地點、由出發時刻、出發地點、到達時刻和到達地點所確定的運用、以及目標日地點，根據地點和時刻將可以連接的節點全部用弧線連接；設定單元，其在從開始日起順次到目標日為止的每天，對每臺車輛，分配用所述弧線連接的所述運用，設定一條連結連接的所述運用的線路；交換單元，其在有車輛在目標日不在目標日地點時，為了使全部的車輛在目標日都在目標日地點，在與多臺車輛相對應的多條線路中以所述弧線為單位與其他的弧線進行交換；和輸出單元，其在發現全部車輛在目標日在目標日地點的多條線路時，將與該線路相對應的運用的分配作為車輛運用計劃輸出。2.根據權利要求l所記載的車輛運用計劃編制裝置，其特徵在於，所述編制單元，在第一節點是與第二節點同一天或翌日的節點、且所述第二節點的到達地點與所述第一節點的出發地點一致、且所述第二節點的到達時刻比所述第一節點的出發時刻早的情況下，可以連接所述第一節點和所述第二節點。3.根據權利要求1或2所記載的車輛運用計劃編制裝置，其特徵在於，所述設定單元，在每天，在有未分配運用的車輛時，對未分配運用的車輛分配滯留在前一天的到達地點的預備節點。4.根據權利要求1或2所記載的車輛運用計劃編制裝置，其特徵在於，所述交換單元，從1起順次設定表示在各線路中的交換的弧線數量的交換次數，為了使與全部線路相對應的全部車輛在目標日在日標日地點，交換弧線直至交換次數閾值。5.根據權利要求4所記載的車輛運用計劃編制裝置，其特徵在於，所述交換單元，從1起順次設定表示在各線路中的交換的弧線數量的交換次數，將從所述交換次數閾值減去交換次數的數作為新閾值，對在目標日不在目標日地點的車輛交換弧線，直至該新閾值。6.根據權利要求1或2所記載的車輛運用計劃編制裝置，其特徵在於，所述交換單元，在有車輛在目標日不在目標日地點、且有車輛具有限定車輛運用的運用限定約束的情況下，進行弧線的交換。7.—種車輛運用計劃編制方法，其特徵在於，編制運用連接圖表，在該運用連接圖表中，在從開始日到目標日的期間，對每臺車輛，分別用節點表示開始日地點、由出發時刻、出發地點、到達時刻和到達地點所確定的運用、以及目標日地點，根據地點和時刻將可以連接的節點全部用弧線連接；在從開始日起順次到目標日為止的每天，對每臺車輛，分配用所述弧線連接的所述運用，設定一條連結連接的所述運用的線路；在有車輛在目標日不在目標日地點時，為了使全部的車輛在目標日都在目標日地點，在與多臺車輛相對應的多條線路中以所述弧線為單位與其他的弧線進行交換；在發現全部車輛在目標日在目標日地點的多條線路時，將與該線路相對應的運用的分配作為車輛運用計劃輸出。8.根據權利要求7所記載的車輛運用計劃編制方法，其特徵在於，編制所述運用連接圖表，是在所述第一節點是與所述第二節點同一天或翌日的節點、且所述第二節點的到達地點與所述第一節點的出發地點一致、且所述第二節點的到達時刻比所迷第一節點的出發時刻早的情況下，可以連接所述第一節點和所述第二節點。9.根據權利要求7或8所記載的車輛運用計劃編制方法，其特徵在於，設定所述線路，是在每天，在有未分配運用的車輛時，對未分配運用的車輛分配滯留在前一天的到達地點的預備節點。10.根據權利要求7或8所記載的車輛運用計劃編制方法，其特徵在於，與所述其他的弧線進行交換，是從1起順次設定表示在各線路中的交換的弧線數量的交換次數，為了使與全部線路相對應的全部車輛在目標日在日標日地點，交換弧線直至交換次數閾值。11.根據權利要求10所記載的車輛運用計劃編制方法，其特徵在於，與所述其他的弧線進行交換的步驟，是從1起順次設定表示在各線路中的交換的弧線數量的交換次數，將從所述交換次數閾值減去交換次數的數作為新閾值，對在目標日不在目標日地點的車輛交換弧線，直至該新閾值。12.根據權利要求7或8所記栽的車輛運用計劃編制方法，其特徵在於，與所述其他的弧線進行交換，是在有車輛在目標日不在目標日地點、且有車輛具有限定車輛運用的運用限定約束的情況下，進行弧線的交換。全文摘要本發明涉及一種車輛運用計劃編制裝置以及方法，目的在於在短時間內自動編制滿足約束的車輛運用表。具備單元(905)，其編制運用連接圖表，在該運用連接圖表中，在從開始日到目標日的期間，對每臺車輛，分別用節點表示開始日地點、由出發時刻、出發地點、到達時刻和到達地點所確定的運用、以及目標日地點，根據地點和時刻將可以連接的節點全部用弧線連接；單元(907)，其在從開始日起順次到目標日為止的每天，對每臺車輛，分配用所述弧線連接的所述運用，設定一條連結連接的所述運用的線路；單元(908)，其在有車輛在目標日不在目標日地點時，為了使全部的車輛在目標日都在目標日地點，在與多臺車輛相對應的多條線路中以所述弧線為單位與其他的弧線進行交換；和輸出單元(103)，在發現全部車輛在目標日在目標日地點的多條線路時，將與該線路相對應的運用的分配作為車輛運用計劃輸。文檔編號G06Q50/00GK101425154SQ20081017078公開日2009年5月6日申請日期2008年10月29日優先權日2007年10月29日發明者大槻知史,愛須英之申請人:株式會社東芝