湖南工业职业技术学院学报
湖南工業職業技術學院學報
호남공업직업기술학원학보
JOURNAL OF HUNAN INDUSTRY POLYTECHNIC
2014年
5期
9-11
,共3页
专用道设置问题%最短路径问题%约束条件%动态%生枝-剪枝算法
專用道設置問題%最短路徑問題%約束條件%動態%生枝-剪枝算法
전용도설치문제%최단로경문제%약속조건%동태%생지-전지산법
lane-reserved problems%shortest path problems%constraints%dynamic%create-and-cut algorithm
专用道设置问题中，将运输任务限定为一个，从而将问题转化为带约束条件的动态最短路径问题。针对该问题的实际特点，设计了生枝-剪枝算法。该算法的核心思想是：穷举所有从起点开始的行驶路径（生枝过程），然后利用剪枝规则剪除不符要求的分枝，最后在抵达终点的行驶路径中经过比较选出最优路径。
專用道設置問題中，將運輸任務限定為一箇，從而將問題轉化為帶約束條件的動態最短路徑問題。針對該問題的實際特點，設計瞭生枝-剪枝算法。該算法的覈心思想是：窮舉所有從起點開始的行駛路徑（生枝過程），然後利用剪枝規則剪除不符要求的分枝，最後在牴達終點的行駛路徑中經過比較選齣最優路徑。
전용도설치문제중，장운수임무한정위일개，종이장문제전화위대약속조건적동태최단로경문제。침대해문제적실제특점，설계료생지-전지산법。해산법적핵심사상시：궁거소유종기점개시적행사로경（생지과정），연후이용전지규칙전제불부요구적분지，최후재저체종점적행사로경중경과비교선출최우로경。
If there is only one transport task in the Lane-reserved Problems, the new problem named Dynamic Shortest Path Problem with Constraints (DSPC) is studied in this paper. From the factual characteristic of DSPC, Create-and-Cut algorithm is introduced. The algorithm is a brute-force algorithm, that is, creating travel-paths (branches) from Source-node for every node in transportation network, cutting undesirable branches by Cutting-Rules, comparing and picking out the optimal travel-path within all travel-paths which arrived at the destination-node.
