================================================= Some Notes on the BAP Greedy Heuristic Algorithms ================================================= LeongHW (Started: Sept 2002; Last Modified Sept 2008) Below are some notes on Greedy Heuristic Algorithms for BAP Partitioning; Your assigned greedy heuristic is given at the end. --------------------------------- Idea 1: Two step greedy approach; --------------------------------- Repeat the following steps: step 1: Select an unassigned vessel v; step 2: Then select the best section, s, for vessel v; Assign vessel v to section s; Pseudo-Code (Two Step Greedy) ----------------------------- begin // Given list of unassigned vessels // list of initially empty sections V := list of unassigned vessels; S := list of sections; while (V not empty) do { v := SelectVessel(V); // select a vessel v from V s := SelectSection(S,v); // select section for vessel v if ( s != NULL) then { Assign vessel v to section s; Update section s; } V := V - {v}; } end; The two step greedy approach is specified by two selection criteria for: (a) selection of a vessel (v) to assign (b) choice of a "best" section s to assign the selected vessel v We list a number of possible selection criteria that you can use: (a) for Vessel Selection: VL = Vessel Length (longest vessel first) CM = Number of Container Moved (most first) DS = Vessel Duration of Stay (longest first) AT = Arrival Time (smallest first) DT = Departure Time (smallest first) (b) for Section Selection (given a vessel v): FF = first fit (first section that "fits") BF = best fit (section that gives best fits for the vessel) WF = worst fit (section that give worst fit for the vessel) TC = section that gives the minimum increase in transshipment cost SD = section that gives the minimum increase in section density ---------------------------------- Idea 2: Minimize Incremental Cost; ---------------------------------- repeat the following: for each unassigned vessel v and each section s, compute Incremental-cost(s,v); For all possible (v,s) combinations, let (v*,s*) be the combination that optimizes Incremental-cost(s,v); assign vessel v* to section s*; until there is no more feasible assignment; Pseudo-Code (Min Incremental Cost) ---------------------------------- begin // Given list of unassigned vessels // list of initially empty sections V := list of unassigned vessels; S := list of sections; repeat min-incr-cost := infinity; for (all vessel v in V) do { for (all section s in S) do { incr-cost := Incremental-cost(s,v); if (incr-cost < min-incr-cost) then { min-incr-cost := incr-cost; min-vessel := v; min-section := s; } } } Assign vessel min-vessel to section min-section; Update section min-section; V := V - {min-vessel}; until (no more vessels can be assigned); end; The incremental cost approach is specified by the cost function to be used. ITC = increase in the (transshipment cost) ISD = increase in the (sum of section densities) ================================= Your assigned Heuristic Algorithm ================================= Student Heuristic Name of Partitioner Usercode --------------------------------------------------------------------------- ADITYA BABEL (VL,FF) [BAPGDY01Partitioner] AB ALEXANDER MOSSIN (CM,BF) [BAPGDY02Partitioner] AM BHOJAN ANAND (DS,WF) [BAPGDY03Partitioner] BA CHEN WEI (AT,TC) [BAPGDY04Partitioner] CW CHEN XIANKUN (DT,SD) [BAPGDY05Partitioner] CX CHENG YUAN (Incremental-ITC) [BAPGDY06Partitioner] CY CHUA YAM SONG (VL,BF) [BAPGDY07Partitioner] CYS DILIP RAJENDRAN (CM,WF) [BAPGDY08Partitioner] DR DONG XINSHU (DS,TC) [BAPGDY09Partitioner] DX FELIX HALIM (AT,SD) [BAPGDY10Partitioner] FH GONG BOZHAO (DT,FF) [BAPGDY11Partitioner] GB HAN WUGUANG (Incremental-ISD) [BAPGDY12Partitioner] HW HOANG THAI DUONG (VL,WF) [BAPGDY13Partitioner] HTD HU AIHONG (CM,TC) [BAPGDY14Partitioner] HA HU JUNFENG (DS,SD) [BAPGDY15Partitioner] HJ LI HONGYANG (AT,FF) [BAPGDY16Partitioner] LH LUONG MINH THANG (DT,BF) [BAPGDY17Partitioner] LMT MAO LEI (Incremental-ITC) [BAPGDY18Partitioner] ML PAN XIANGRUI (VL,TC) [BAPGDY19Partitioner] PX PNG SHAO WEI (CM,SD) [BAPGDY20Partitioner] PSW QI DAWEI (DS,FF) [BAPGDY21Partitioner] QD SANDEEP KUMAR (AT,BF) [BAPGDY22Partitioner] SK SHI CHENWEI (DT,WF) [BAPGDY23Partitioner] SC TRAN DUY THAO (Incremental-ISD) [BAPGDY24Partitioner] TDT WANG CHUNDONG (VL,SD) [BAPGDY25Partitioner] WC WANG GUOPING (CM,FF) [BAPGDY26Partitioner] WG WANG XIAOXI (DS,BF) [BAPGDY27Partitioner] WX WANG YUE (AT,WF) [BAPGDY28Partitioner] WY WON KOK SUNG (DT,TC) [BAPGDY29Partitioner] WKS WONG AI QI GRACE (Incremental-ITC) [BAPGDY30Partitioner] WAQG XIAO FENG (VL,FF) [BAPGDY31Partitioner] XF XU YIN (CM,BF) [BAPGDY32Partitioner] XY YU JIAN XING (DS,WF) [BAPGDY33Partitioner] YJX ZHANG CHENYU (AT,TC) [BAPGDY34Partitioner] ZC ZHENG HANXIONG (DT,SD) [BAPGDY35Partitioner] ZH ZHONG XIAOHU (Incremental-ISD) [BAPGDY36Partitioner] ZX ZHOU SHAOPING (VL,BF) [BAPGDY37Partitioner] ZS ZHOU ZENAN (CM,WF) [BAPGDY38Partitioner] ZZ ------------------------------------------------------------- Greedy: [VL, CM, DS, AT, DT] x [FF, BF, WF, TC, SD] v [Incr-ITC, Incr-ISD] ---------------------- (CS5206, LeongHW)