帶衝突裝箱問題的高性能最佳化算法研究

《帶衝突裝箱問題的高性能最佳化算法研究》是依託上海大學，由蓋玲擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：帶衝突裝箱問題的高性能最佳化算法研究
• 項目類別：青年科學基金項目
• 項目負責人：蓋玲
• 依託單位：上海大學

中文摘要

裝箱問題是經典的組合最最佳化問題之一，傳統的裝箱問題考慮的是對於給定的一組（序列）物品，如何安排裝箱方式使得所用箱子數目最少。在設計裝箱時，主要的難點是如何協調安排不同尺寸的物品，使箱子的容量限制得到滿足並儘可能裝滿。1999年Klaus Jansen提出的帶衝突裝箱問題（Bin Packing with Conflicts）模型，更加貼近生活生產實際，考慮到物品之間可能存在衝突關係，如何避免衝突同時使用箱子數目儘可能少，是近年來裝箱問題研究領域的重要分支之一。在帶衝突裝箱問題中，物品間的衝突關係一般由圖給定，稱為衝突圖。到目前為止，文獻中考慮的衝突圖基本都限制在可以多項式時間求解色數的圖上。本項目的研究重點，是把衝突圖進行推廣，主要考慮賦權圖、有向圖及線上情形下的帶衝突裝箱問題，對問題計算複雜性進行分析，並設計新算法，通過分析近似比（競爭比）來保證最佳化算法的高性能表現。

結題摘要

帶衝突裝箱問題是近年來組合最佳化領域重要的研究方向之一，並有了越來越廣泛的實際套用。傳統情形下，衝突主要體現在物品、網路等非生命體的最佳化安排中，“人”的調度和安排中套用比較少。我們在項目研究的進展過程中注意到，帶衝突裝箱問題在醫療管理中的套用十分關鍵，這也給本項目的研究帶來了新的生命力。 我們從以下三類問題出發對帶衝突裝箱問題展開研究： （1）賦權圖下的帶衝突裝箱問題。在最初提出的帶衝突裝箱問題模型中，不允許相互衝突的物品放到一個箱子裡去。但實際生活中可能會出現不得不“容忍”的情況，比如運輸問題中車輛數量有限，不得不把衝突物品放到一個車輛里，但可能需要額外附加防護措施。這裡就出現了費用的增加或者容忍限度的問題。主要考慮了如下兩個模型： 模型Ⅰ：每個箱子除了容量限制之外，還有一定的衝突容忍度。物品間的衝突關係及衝突“嚴重程度”可以通過賦權的衝突圖表現。圖中的每個頂點仍然代表物品，兩點之間若有邊相連，則表示兩物品間存在衝突，邊上的權重代表這兩個物品間的衝突值。只要放入一個箱子內物品的衝突值之和不超過該箱子的容忍度即為合理裝箱。目標是最小化使用箱子的個數。 模型Ⅱ：從費用的角度對帶衝突裝箱問題進行考慮。假設物品之間的衝突費用介於0，1 之間，這個費用仍由衝突圖中相應兩點之間邊的權重確定。箱子的使用費用為1，衝突容忍度也是1。目標是尋找一種合理裝箱方式，使得產生的總費用最小，即箱子費用和衝突費用之和最小。 （2）有向圖下的帶衝突裝箱問題。實際生活中很多問題的衝突關係是單向的，比如病人做多項檢查治療，驗血需要空腹，而吊水則需要飲食後，所以驗血可以安排在吊水之前，而吊水之後短時間內是不能進行驗血的。類似更常見的例子還有很多，比如快遞箱打包時也會把堅固耐壓的物品放在下面，柔軟易碎的物品放在上面等。 （3）線上情形下的帶衝突裝箱問題。當需要裝箱的物品信息事先並不能完全得知，就需要考慮線上情形下的最佳化問題：物品按時間（或按序）到達，其尺寸及與其他物品的衝突關係均在到達後方能得知，要求物品到達後立即安排裝箱，並且不可悔改，目標是使用的箱子個數儘可能少。 在本項目的研究中，我們針對以上四類帶衝突裝箱問題進行算法設計與分析，研究問題的計算複雜性，並通過數值計算協助分析算法的性能。