src/inform-or/genetic_algorithm_inform/best_match_heuristic.py

   1 # Best Match Heuristic based on the paper by Li et al. (2014)
   2 from gurobipy import multidict
   3 from generator_parser import parse_file
   4 from operator import itemgetter
   5 from ems import EMS
   6 from item import Item
   7 import time
   8
   9
  10 # list for all ems (first element refers to box)
  11 ems_list = []
  12 item_list = []
  13 box_list = []
  14
  15
  16 def initializeEMS(box, length_box, width_box, height_box):
  17
  18     '''
  19     used to initialize the first EMS of a box. This EMS has the exact same dimensions as the (empty) box itself
  20     :param box: box for which an initalization EMS should be created and located it
  21     :return: EMS with dimensions of the box it is located in
  22     '''
  23     global boxcounter
  24     boxcounter += 1
  25     return EMS(boxcounter, length_box[box[0]], width_box[box[0]], height_box[box[0]], 0, 0, 0)
  26
  27
  28 def deleteEmptyEMS():
  29
  30     '''
  31     this function will delete all EMS that got created with a volume of <= 0
  32     '''
  33     for ems in ems_list:
  34         if ems.volume <= 0:
  35             ems_list.remove(ems)
  36
  37
  38 def checkEMSintersect(curr_ems, change_x, change_y, change_z):
  39
  40     '''
  41     this function will update EMS that get intersected by a newly placed item
  42     :param curr_ems: current EMS, in which the item got placed in (this is used to determine the max and min coordinates of the item)
  43     :param change_x: dimension of the item in x direction
  44     :param change_y: dimension of the item in y direction
  45     :param change_z: dimension of the item in z direction
  46     '''
  47     item_max_x = curr_ems.min_x + change_x
  48     item_max_y = curr_ems.min_y + change_y
  49     item_max_z = curr_ems.min_z + change_z
  50
  51     ems_list_copy = ems_list[:]
  52     for ems in ems_list_copy:
  53         if ems != curr_ems:
  54             if ems.box == curr_ems.box:
  55                 if (ems.min_x < item_max_x <= ems.max_x) and (ems.min_y < item_max_y <= ems.max_y) and (ems.min_z < item_max_z <= ems.max_z):
  56                     # six new EMS, limited by the different item dimension
  57                     # min_x
  58                     ems_list.append(EMS(ems.box, curr_ems.min_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
  59                     # min_y
  60                     ems_list.append(EMS(ems.box, ems.max_x, curr_ems.min_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
  61                     # min_z
  62                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, curr_ems.min_z, ems.min_x, ems.min_y, ems.min_z))
  63                     # max_x
  64                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, item_max_x, ems.min_y, ems.min_z))
  65                     # max_y
  66                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, item_max_y, ems.min_z))
  67                     # max_z
  68                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, item_max_z))
  69                     ems_list.remove(ems)
  70
  71                 if (ems.min_x <= curr_ems.min_x < ems.max_x) and (ems.min_y <= curr_ems.min_y < ems.max_y) and (ems.min_z <= curr_ems.min_z < ems.max_z):
  72                     # six new EMS, limited by the different item dimension
  73                     # min_x
  74                     ems_list.append(EMS(ems.box, curr_ems.min_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
  75                     # min_y
  76                     ems_list.append(EMS(ems.box, ems.max_x, curr_ems.min_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
  77                     # min_z
  78                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, curr_ems.min_z, ems.min_x, ems.min_y, ems.min_z))
  79                     # max_x
  80                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, item_max_x, ems.min_y, ems.min_z))
  81                     # max_y
  82                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, item_max_y, ems.min_z))
  83                     # max_z
  84                     ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, item_max_z))
  85                     if ems in ems_list:
  86                         ems_list.remove(ems)
  87
  88                 deleteEmptyEMS()
  89
  90
  91 def checkEMSpierce(curr_ems, change_x, change_y, change_z):
  92
  93     '''
  94     this function will update EMS that get pierced by a newly placed item
  95     :param curr_ems: current EMS, in which the item got placed in (this is used to determine the max and min coordinates of the item)
  96     :param change_x: dimension of the item in x direction
  97     :param change_y: dimension of the item in y direction
  98     :param change_z: dimension of the item in z direction
  99     '''
 100     item_max_x = curr_ems.min_x + change_x
 101     item_max_y = curr_ems.min_y + change_y
 102     item_max_z = curr_ems.min_z + change_z
 103
 104     ems_list_copy = ems_list[:]
 105     for ems in ems_list_copy:
 106         if ems != curr_ems:
 107             if ems.box == curr_ems.box:
 108                 # min_coordinate
 109                 if ems.min_x <= curr_ems.min_x < ems.max_x and ems.min_y <= curr_ems.min_y < ems.max_y:
 110                     if curr_ems.min_z <= ems.min_z < item_max_z:
 111                         # three new EMS, limited by the different item dimension
 112                         # max_z (behind)
 113                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, item_max_z))
 114                         # min_y (left)
 115                         ems_list.append(EMS(ems.box, ems.max_x, curr_ems.min_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
 116                         # min_x (below)
 117                         ems_list.append(EMS(ems.box, curr_ems.min_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
 118                         # delete EMS
 119                         if ems in ems_list:
 120                             ems_list.remove(ems)
 121
 122                 if ems.min_x <= curr_ems.min_x < ems.max_x and ems.min_z <= curr_ems.min_z < ems.max_z:
 123                     if curr_ems.min_y <= ems.min_y < item_max_y:
 124                         # three new EMS, limited by the different item dimension
 125                         # max_y (behind)
 126                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, item_max_y, ems.min_z))
 127                         # min_x (left)
 128                         ems_list.append(EMS(ems.box, curr_ems.min_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
 129                         # min_z (below)
 130                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, curr_ems.min_z, ems.min_x, ems.min_y, ems.min_z))
 131                         # delete EMS
 132                         if ems in ems_list:
 133                             ems_list.remove(ems)
 134
 135                 if ems.min_y <= curr_ems.min_y < ems.max_y and ems.min_z <= curr_ems.min_z < ems.max_z:
 136                     if curr_ems.min_x <= ems.min_x < item_max_x:
 137                         # three new EMS, limited by the different item dimension
 138                         # max_x (behind)
 139                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, item_max_x, ems.min_y, ems.min_z))
 140                         # min_y (left)
 141                         ems_list.append(EMS(ems.box, ems.max_x, curr_ems.min_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
 142                         # min_z (below)
 143                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, curr_ems.min_z, ems.min_x, ems.min_y, ems.min_z))
 144                         # delete EMS
 145                         if ems in ems_list:
 146                             ems_list.remove(ems)
 147
 148                 # max_coordinate
 149                 if ems.min_x < item_max_x <= ems.max_x and ems.min_y < item_max_y <= ems.max_y:
 150                     if curr_ems.min_z < ems.max_z <= item_max_z:
 151                         # three new EMS, limited by the different item dimension
 152                         # min_z (in front)
 153                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, curr_ems.min_z, ems.min_x, ems.min_y, ems.min_z))
 154                         # max_y (right)
 155                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, item_max_y, ems.min_z))
 156                         # max_x (on top)
 157                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, item_max_x, ems.min_y, ems.min_z))
 158                         # delete EMS
 159                         if ems in ems_list:
 160                             ems_list.remove(ems)
 161
 162                 if ems.min_x < item_max_x <= ems.max_x and ems.min_z < item_max_z <= ems.max_z:
 163                     if curr_ems.min_y < ems.max_y <= item_max_y:
 164                         # three new EMS, limited by the different item dimension
 165                         # min_y (in front)
 166                         ems_list.append(EMS(ems.box, ems.max_x, curr_ems.min_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
 167                         # max_x (right)
 168                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, item_max_x, ems.min_y, ems.min_z))
 169                         # max_z (on top)
 170                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, item_max_z))
 171                         # delete EMS
 172                         if ems in ems_list:
 173                             ems_list.remove(ems)
 174
 175
 176                 if ems.min_y < item_max_y <= ems.max_y and ems.min_z < item_max_z <= ems.max_z:
 177                     if curr_ems.min_x < ems.max_x <= item_max_x:
 178                         # three new EMS, limited by the different item dimension
 179                         # min_x (in front)
 180                         ems_list.append(EMS(ems.box, curr_ems.min_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, ems.min_z))
 181                         # max_y (right)
 182                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, item_max_y, ems.min_z))
 183                         # max_z (on top)
 184                         ems_list.append(EMS(ems.box, ems.max_x, ems.max_y, ems.max_z, ems.min_x, ems.min_y, item_max_z))
 185                         # delete EMS
 186                         if ems in ems_list:
 187                             ems_list.remove(ems)
 188
 189                 deleteEmptyEMS()
 190
 191
 192 def checkEMSinside():
 193
 194     '''
 195     check if one EMS is completely inside another EMS and if yes, delete the smaller one
 196     '''
 197     for ems1 in ems_list:
 198         for ems2 in ems_list:
 199             if ems1 != ems2:
 200                 if ems1.min_x <= ems2.min_x <= ems1.max_x and ems1.min_x <= ems2.max_x <= ems1.max_x:
 201                     if ems1.min_y <= ems2.min_y <= ems1.max_y and ems1.min_y <= ems2.max_y <= ems1.max_y:
 202                         if ems1.min_z <= ems2.min_z <= ems1.max_z and ems1.min_z <= ems2.max_z <= ems1.max_z:
 203                             ems_list.remove(ems2)
 204
 205
 206 def updateEMS(curr_ems, coor, change):
 207
 208     '''
 209     calculates new EMS dimensions based on the given EMS, coordinate length decrease (change) in that direction
 210     :param curr_ems: EMS that will get updated
 211     :param coor: dimension in which the EMS should get updated
 212     :param change: Length by which the EMS will get changed
 213     :return: new EMS object with updated dimensions
 214     '''
 215     tmpmax_x = curr_ems.max_x
 216     tmpmax_y = curr_ems.max_y
 217     tmpmax_z = curr_ems.max_z
 218     if coor == 'x':
 219         tmpmin_x = curr_ems.min_x + change
 220         tmpmin_y = curr_ems.min_y
 221         tmpmin_z = curr_ems.min_z
 222     elif coor == 'y':
 223         tmpmin_x = curr_ems.min_x
 224         tmpmin_y = curr_ems.min_y + change
 225         tmpmin_z = curr_ems.min_z
 226     elif coor == 'z':
 227         tmpmin_x = curr_ems.min_x
 228         tmpmin_y = curr_ems.min_y
 229         tmpmin_z = curr_ems.min_z + change
 230
 231     # returns initialization of new EMS, output needs to be saved as a new EMS object
 232     return EMS(curr_ems.box, tmpmax_x, tmpmax_y, tmpmax_z, tmpmin_x, tmpmin_y, tmpmin_z)
 233
 234
 235 def checkOrientations(orientation, ems, item, length_item, width_item, height_item):
 236
 237     '''
 238     checks whether the item fits in the ems with the current orientation or not
 239     :param orientation: orientation that should be checked
 240     :param ems: EMS in which the item is to be placed in
 241     :param item: item to be placed into the EMS
 242     :return: item, ems, orientation, calculated volume_ratio (volume_item/volume_ems) and min_margin
 243     '''
 244     if orientation == 1:
 245         x = length_item[item[0]]
 246         y = width_item[item[0]]
 247         z = height_item[item[0]]
 248     elif orientation == 2:
 249         x = length_item[item[0]]
 250         y = height_item[item[0]]
 251         z = width_item[item[0]]
 252     elif orientation == 3:
 253         x = width_item[item[0]]
 254         y = length_item[item[0]]
 255         z = height_item[item[0]]
 256     elif orientation == 4:
 257         x = width_item[item[0]]
 258         y = height_item[item[0]]
 259         z = length_item[item[0]]
 260     elif orientation == 5:
 261         x = height_item[item[0]]
 262         y = length_item[item[0]]
 263         z = width_item[item[0]]
 264     else:
 265         x = height_item[item[0]]
 266         y = width_item[item[0]]
 267         z = length_item[item[0]]
 268
 269     # check if item fits into EMS. If yes, return item, ems, orientation, volume ratio and the min margin, otherwise pass
 270     if ems.min_x + x <= ems.max_x:
 271         if ems.min_y + y <= ems.max_y:
 272             if ems.min_z + z <= ems.max_z:
 273                 # calculate volume ratio (volume_item/volume_ems)
 274                 volume_item = x * y * z
 275                 volume_ems = ems.volume
 276                 volume_ratio = volume_item/volume_ems
 277
 278                 # calculate margin in each direction and determine the smallest margin (min_margin)
 279                 x_margin = ems.length - x
 280                 y_margin = ems.width - y
 281                 z_margin = ems.height - z
 282
 283                 min_margin = min(x_margin, y_margin, z_margin)
 284                 return (item, ems, orientation, volume_ratio, min_margin)
 285
 286
 287 def orientationCheck(orientation, item, length_item, width_item, height_item):
 288
 289     '''
 290     'standardize' dimensions of items to allow easier calculations
 291     :param orientation: orientation in which the item is to be placed
 292     :param item: item which is to be placed
 293     :return: standardized dimensions in x, y and z direction
 294     '''
 295     if orientation == 1:
 296         change_x = length_item[item]
 297         change_y = width_item[item]
 298         change_z = height_item[item]
 299     elif orientation == 2:
 300         change_x = length_item[item]
 301         change_y = height_item[item]
 302         change_z = width_item[item]
 303     elif orientation == 3:
 304         change_x = width_item[item]
 305         change_y = length_item[item]
 306         change_z = height_item[item]
 307     elif orientation == 4:
 308         change_x = width_item[item]
 309         change_y = height_item[item]
 310         change_z = length_item[item]
 311     elif orientation == 5:
 312         change_x = height_item[item]
 313         change_y = length_item[item]
 314         change_z = width_item[item]
 315     else:
 316         change_x = height_item[item]
 317         change_y = width_item[item]
 318         change_z = length_item[item]
 319
 320     return change_x, change_y, change_z
 321
 322
 323 def best_match_heuristic(generation, consideredBoxes, consideredEMS, length_item, width_item, height_item, length_box, width_box, height_box, weight_item, best_chromosome = False):
 324
 325     '''
 326     the main function of the best match heuristic
 327     :param generation: current generation, which should be evaluated
 328     :best_chromosome: indicates to save the item coordinates for visualization purposes
 329     :return: generation with appeneded fitness value for each chromosome, if best_chromosome = True, also a list of the placed item objects and used boxes
 330     '''
 331     # check each chromosome in a given generation
 332     #print(generation)
 333     for chromosome in generation:
 334         del ems_list[:]
 335         startTime = time.time()
 336         global boxcounter
 337         boxcounter = 0
 338         if chromosome.fitness == None or best_chromosome == True:
 339             OC = [] # list of opened containers
 340             P = [] # packing sequence
 341             BPS = chromosome.BPS[:]
 342             CLS = chromosome.CLS[:]
 343             boxpacking = []
 344             boxplaced = False
 345             while BPS != []:
 346                 boxplaced = False
 347                 # check each opened box
 348                 for c in OC:
 349                     # list of EMSs in the current box c
 350                     curr_box_ems_list = []
 351                     for element in ems_list:
 352                         if element.box == c[1]:
 353                             curr_box_ems_list.append(element)
 354                     curr_box_ems_list.sort(key=lambda x: x.min_vertex)
 355                     j = 1
 356                     while j <= len(curr_box_ems_list) and boxplaced == False:
 357                         k = j + consideredEMS
 358                         while j < k and j <= len(curr_box_ems_list):
 359                             for i in range(0, consideredBoxes):
 360                                 if i <= len(BPS)-1:
 361                                     for l in range(1,7):
 362                                         # check if placement is possible. If yes, place item with feasible orientation and min. margin into the box, otherwise pass
 363                                         possiblePlacement = checkOrientations(orientation=l, ems=curr_box_ems_list[j-1], item=BPS[i], length_item=length_item, width_item=width_item, height_item=height_item)
 364                                         if possiblePlacement != None:
 365                                             P.append(possiblePlacement)
 366                             j += 1
 367                         if P != []:
 368                             # sort P in terms of volume_ratio and min_margin, pack the first (best) possiblePlacement, get orientation and remove item from BPS list
 369                             P.sort(key = lambda y: (-y[3], y[4]))
 370                             boxpacking.append((P[0][0], P[0][1].box))
 371                             change_x, change_y, change_z = orientationCheck(orientation=P[0][2], item=P[0][0][0], length_item=length_item, width_item=width_item, height_item=height_item)
 372                             BPS.remove(P[0][0])
 373
 374                             # save coordinates for best chromosome in last generation for visualization
 375                             if best_chromosome == True:
 376                                 item_list.append(Item(P[0][0], P[0][1].box, P[0][1].min_x, P[0][1].min_y, P[0][1].min_z, change_x, change_y, change_z))
 377
 378                             # update the EMS in which the current item is placed in. This creates three new EMSs
 379                             ems_list.append(updateEMS(P[0][1], 'x', change_x))
 380                             ems_list.append(updateEMS(P[0][1], 'y', change_y))
 381                             ems_list.append(updateEMS(P[0][1], 'z', change_z))
 382
 383                             # check if new EMS cut any other EMSs, if yes update these EMSs
 384                             checkEMSintersect(P[0][1], change_x, change_y, change_z)
 385                             checkEMSpierce(P[0][1], change_x, change_y, change_z)
 386                             ems_list.remove(P[0][1])
 387                             # check if one EMS is completely inside an other EMS and if any empty EMSs (volume = 0) exist
 388                             checkEMSinside()
 389                             deleteEmptyEMS()
 390
 391                             # delete list of possible Placements, set boxplaced to True
 392                             del P[:]
 393                             boxplaced = True
 394
 395                     if boxplaced == True:
 396                         break
 397
 398                 while CLS != [] and boxplaced == False:
 399                     # open a new box
 400                     ems_list.append(initializeEMS(box=CLS[0], length_box=length_box, width_box=width_box, height_box=height_box))
 401                     OC.append(CLS[0])
 402                     CLS.pop(0)
 403                     # try to pack the first kb boxes into the new box
 404                     for i in range(0, consideredBoxes):
 405                         if i <= len(BPS)-1:
 406                             for l in range(1,7):
 407                                 # check if placement is possible. If yes, place item with feasible orientation and min. margin into the box, otherwise pass
 408                                 possiblePlacement = checkOrientations(orientation=l, ems=ems_list[-1], item=BPS[i], length_item=length_item, width_item=width_item, height_item=height_item)
 409                                 if possiblePlacement != None:
 410                                     P.append(possiblePlacement)
 411
 412                     if P != []:
 413                         # sort P in terms of volume_ratio and min_margin, pack the first (best) possiblePlacement, get orientation and remove item from BPS list
 414                         P.sort(key = lambda y: (-y[3], y[4]))
 415                         boxpacking.append((P[0][0], (P[0][1].box)))
 416                         change_x, change_y, change_z = orientationCheck(orientation=P[0][2], item=P[0][0][0], length_item=length_item, width_item=width_item, height_item=height_item)
 417                         BPS.remove(P[0][0])
 418
 419                         # save coordinates for best chromosome in last generation for visualization
 420                         if best_chromosome == True:
 421                             item_list.append(Item(P[0][0], P[0][1].box, P[0][1].min_x, P[0][1].min_y, P[0][1].min_z, change_x, change_y, change_z))
 422
 423                         # update the EMS in which the current item is placed in. This creates three new EMSs
 424                         ems_list.append(updateEMS(P[0][1], 'x', change_x))
 425                         ems_list.append(updateEMS(P[0][1], 'y', change_y))
 426                         ems_list.append(updateEMS(P[0][1], 'z', change_z))
 427
 428                         # check if new EMS cut any other EMSs, if yes update these EMSs
 429                         checkEMSintersect(P[0][1], change_x, change_y, change_z)
 430                         checkEMSpierce(P[0][1], change_x, change_y, change_z)
 431                         ems_list.remove(P[0][1])
 432                         # check if one EMS is completely inside an other EMS and if any empty EMSs (volume = 0) exist
 433                         checkEMSinside()
 434                         deleteEmptyEMS()
 435
 436                         # delete list of possible Placements, set boxplaced to True
 437                         del P[:]
 438                         boxplaced = True
 439
 440             if boxplaced == False:
 441                 return None
 442
 443             # calculation of fitness (volume ratio of cumulated items and boxes)
 444             vol_items = 0
 445             vol_boxes = 0
 446             used_boxes = []
 447             # determine cumulated volume of items (vol_items) and boxes (vol_boxes)
 448             for item in boxpacking:
 449                 vol_items += (length_item[item[0][0]] * width_item[item[0][0]] * height_item[item[0][0]])
 450                 used_boxes.append(item[1])
 451             for box in OC:
 452                 if box[1] in used_boxes:
 453                     vol_boxes += (length_box[box[0]] * width_box[box[0]] * height_box[box[0]])
 454                     if best_chromosome == True:
 455                         box_list.append(box)
 456
 457             # calculate fitness as the volume ratio and set the EMSs object attributes fitness and packing_sequence
 458             fitness = vol_items/vol_boxes
 459             chromosome.set_packing_sequence(boxpacking)
 460
 461             itemsPerBox = {}
 462             weightBoxes = {}
 463
 464             # calculate total box weights
 465             for i in range(len(chromosome.packing_sequence)):
 466
 467                 # create dictionary with all items in each used box
 468                 if chromosome.packing_sequence[i][1] in itemsPerBox:
 469                     itemsPerBox[chromosome.packing_sequence[i][1]].append(chromosome.packing_sequence[i][0][0])
 470                 else:
 471                     itemsPerBox[chromosome.packing_sequence[i][1]] = [chromosome.packing_sequence[i][0][0]]
 472
 473             for box in itemsPerBox:
 474                 boxtuple = chromosome.CLS[box-1]
 475                 boxweight = 0
 476                 for i in itemsPerBox[box]:
 477                     boxweight += weight_item[i]
 478
 479                 weightBoxes[boxtuple] = boxweight
 480
 481             totalCost = 0
 482             for box in weightBoxes:
 483                 if box[0] == 'B0' or box[0] == 'B1':
 484                     if weightBoxes[box] <= 2000:
 485                         totalCost += 3.79
 486                     elif weightBoxes[box] <= 5000:
 487                         totalCost += 5.99
 488                     elif weightBoxes[box] <= 10000:
 489                         totalCost += 8.49
 490                     elif weightBoxes[box] <= 31500:
 491                         totalCost += 16.08
 492                     else:
 493                         totalCost += 25
 494                 else:
 495                     if weightBoxes[box] <= 5000:
 496                         totalCost += 5.99
 497                     elif weightBoxes[box] <= 10000:
 498                         totalCost += 8.49
 499                     elif weightBoxes[box] <= 31500:
 500                         totalCost += 16.08
 501                     else:
 502                         totalCost += 25
 503
 504             chromosome.set_costs(totalCost)
 505             chromosome.set_fitness(fitness)
 506
 507         else:
 508             # no packing needed, because already done before (e.g. unchanged chromosome)
 509             pass
 510
 511     generation.sort(key=lambda x: x.fitness, reverse=True)
 512     elapsedTime = time.time() - startTime
 513     if best_chromosome == True:
 514         return generation, item_list, box_list
 515     else:
 516         return generation