一些應用領域看到的問題

03-31

最近比較關注一些應用領域的問題. 因為發現我的技能可以用來真的解決應用領域的問題.

所以我來隨便說幾個有意思的:

美國貨車司機問題

一個美國的貨車司機在 $[0,x_n]$ 上開車.

司機開始於0點只能向前開. 車速1小時1 unit of distance.

路上依次有 $x_1,...,x_n$ n個城市, 以及對應每個 $x_i$ 有個時間區間 $[a_i,b_i]$ , 只能在那個時間區間從那裡拿貨物.

但是由於美國的法律原因. 司機開車 $d$ 小時必須要休息. 工作了 $w$ 小時必須要休息. (停住不動但是不在休息算工作). 開了 $d$ 小時或者工作了 $w$ 小時(whichever comes first)必須休息至少 $r$ 小時. 休息的時候不移動. 任何時候可以開始休息, 只是一次休息必須至少 $r$ 小時.

拿貨物的要求是說在 $[a_i,b_i]$ 的時間中有一個時間貨車司機在 $x_i$ , 並且在工作狀態. 比如如果早到了 $x_i$ , 一個可能就是等到 $a_i$ 的時候才能離開 $x_i$ .

問司機能不能在滿足上麵條件從 $0$ 開到 $x_n$ 拿到所有的貨物. 簡單起見我們假設 $rleq w$ .

最早有 $O(n^3)$ 演算法. 後來有人提升到 $O(n^2)$ . 不知道能不能做的更好. 但感覺計算幾何加數據結構做得好的也能直接獲得一個 $O(n^2)$ 的演算法. 我感覺可能會比他們現在的演算法簡單易懂一點.

做這方面研究的人(Asvin Goel)發了不少paper. 比如還有(歐盟/澳大利亞/加拿大)貨車司機問題.

建立在滑塊類遊戲的自動儲存系統

想像一個建立在滑塊遊戲上的儲存系統. 這裡有個錄像. 有點像超級簡單版本的華容道.

https://www.zhihu.com/video/963125461458649088 Naval Research Logistics (NRL)?

onlinelibrary.wiley.com

這個領域有一大堆問題可以做, 比如如果一次要取幾個物品如何最快? 這文章作者之一Kevin Gue的博客頁蠻有意思的, 可以發現一堆問題.

海邊橋式起重機的問題

想像有一個起重機(吊機)和2個碼頭a和b(比如左邊的碼頭和右邊的之類的...或者一個是碼頭一個是火車站...).

現在有兩種request.

這裡R和S都是 ${a,b}$ 的子集.
1. 存貨(S,x): 從S拿到貨物(可以想像這個貨物在S都有一個copy, 可以任意取), 存到地點x.
2. 取貨(R,y): 從地點y取出貨物, 送到R.

所以吊機很久以前可以單獨的做這兩個事情. 比如完成一個存貨, 回到原點, 然後做一個取貨活動. 但是大家發現有個更好的方法, 先存貨, 然後直接去執行一個取貨. 速度會更快.

所以現在的吊機可以做下面的東西:

存取貨(u,x,y,v), 這裡 $u,vin {a,b}$ . 將會從u取貨物, 移動到x, 放下(所以一個存貨operation), 然後移動到y, 取出貨物, 送到v. (所以一個取貨operation).

這裡如果其中一個y或者x不存在的話, 就說明只做一個存貨或者只做一個取貨的operation.

演算法問題的輸入是一堆存貨和取貨的opeartion, 以及任意兩個地方的移動時間. 輸出是一堆吊機的存取貨opearation. 使得吊機完成所有的operation速度最快.

這個問題是可以多項式時間解決的.

Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot Automated Storage/Retrieval System?

pubsonline.informs.org

時間複雜度有點誇張就是了, $O(n^6)$ . 為啥說海邊? 因為應用場景和現在那個文章的第一作者是海運方向的. 當然這個複雜度可以提升到 $O(n^4)$ , 並且generalize到k個碼頭的版本.

垃圾箱問題

有2種車子, 從垃圾場出去, 到不同的地方拉垃圾回垃圾場. 第一種車子可以拉一個垃圾箱, 一種車子可以拉兩個垃圾箱. 比如第二種車子, 一般是從垃圾場開出去, 弄到兩個垃圾箱, 再開回來. 目標是用最少的費用把所有的垃圾箱拉回來.

input是有垃圾點的地方有多少垃圾箱, 以及之間的距離. 而費用是根據車子的種類的權值乘以距離的. 這裡如果有一個可以拉三個垃圾箱的車子, 問題就NP-hard了. 但是這個版本能很容易的reduce到matching問題. 這個問題的paper可以看這裡.

Complexity and Reducibility of the Skip Delivery Problem?

pubsonline.informs.org

可以看出這個問題和前面的海運問題幾乎一模一樣. 我們可以考慮做有多個垃圾場的版本. 也是對於常數個垃圾場可以多項式時間內解出來. 但是可以得到一堆變種. 比如每個垃圾站有capacity, 不能往裡面無限的扔垃圾之類的.

Bonus: 這是一個不結合實際空想問題的話, 優化的結果可能不是現實的人想要的. 快遞公司優化送快件的時候, 我原先以為優化的就是時間, 最短時間送出所有快件之類的. 送快件的時候, 快件小哥賺的錢是送的快件的個數. 只優化時間可能會導致某些小哥送出超級多快件, 某些送出一點點但是還是跑了一整天. 導致快件小哥的不滿. 所以快遞公司優化的時候保證時間少的同時也讓每個快件小哥送的快件個數差不多.

我最近在大陸哪裡都能去. 在大陸有類似的問題可以找我來合作, 我喜歡解決一些看起來有趣的問題. 因為個人品味因素, 我只對有多項式時間解的問題有興趣. 對於已經證明了是NP-hard的問題我就懶得關心了.

P.S.

如果你是搞IEOR/MS/transportation的看我主頁會懷疑我有沒有能力做這方面的東西. 的確我不是這些領域的內行還是新人. 能證明credential的估計只是一個在mathematical programming上的文. 我還submit了理論上更強一點的文給MP, 以及在準備2個可能發Transportation science的東西. 但是這些畢竟還沒出來...