戴瑞勇
華東理工大學
起重電機專業生產廠家無錫宏達2022年4月23日訊 隨著社會的發展與進步,物流調度、路徑導航和無人駕駛等技術在日常生產生活中起著越來越重要的作用,吸引了眾多數學和經濟學家的關注。本文研究了多車輛情況下的塔式起重機問題（Stacker Crane Problem）,提出了相應的近似算法。問題的輸入由一個包含頂點集V,邊集E和弧集A的混合圖G=（V,E,A）和一個定義在E∪A上的非負整數費用函數c組成。根據不同的優化目標,本文考慮以下四個問題:
（一）k-倉庫塔式起重機問題（k-DSCP）。給定一個包含k個不同倉庫點的集合D（?）V,目標是找到一系列包含弧集A中所有弧的k條回路（closed walks）且使得回路的總費用最小。每條回路對應一個車輛的行駛路線,并且必須從一個不同的倉庫點出發再返回到這個倉庫點。
（二）k-塔式起重機問題（k-SCP）。不給定固定倉庫點,車輛可以從任意頂點出發,然后返回相應的出發點。目標是找到一系列包含弧集A中所有弧的k條回路且使得回路的總費用最小。
（三）k-倉庫塔式起重機路問題（k-DSCPP）。給定一個包含k個不同倉庫點的集合D（?）V,目標是找到一系列包含弧集A中所有弧的k條路徑（open walks）且使得路徑的總費用最小。車輛必須從一個不同的倉庫點出發但可以在任意頂點停下。
（四）k-塔式起重機路問題（k-SCPP）。不給定固定倉庫點,車輛可以從任意頂點出發,也可以在任意頂點停下。目標是找到一系列包含弧集A中所有弧的k條路徑且使得路徑的總費用最小。
針對以上四個問題,本文分別提出了常數界的近似算法。具體來說,針對k-DSCP、k-SCP和k-DSCPP,本文首先分別給出了一個3-近似算法。如果弧費用是對稱的,即對于圖G中的每條弧,G中都有一條費用不大于這條弧的平行邊,本文分別給出了具有更好近似比的算法。算法的近似比分別為max{9/5,2-1/2k+1}、2和2。對于k=SCPP,本文首先給出了一個針對弧費用滿足對稱性條件的2-近似算法。接著,對于k-SCPP在k=1時的一個特例,即SCPP,本文給出了一個適用于所有實例的3-近似算法和一個針對弧費用滿足對稱性條件的9/5-近似算法。其中,除了三個2-近似算法的復雜度為O（|V|2log|V|）,上述所有算法均可以在O（|V|3）時間內運行。
|
