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