In your textbook, consider Exercise 5.9 at the end of Chapter 5 related to the 1-Dimensional Bin Packing Problem with Heterogeneous Fleet. 1) Create a heuristic for the 1-Dimensional Bin Packing Problem with Heterogeneous Fleet. Describe the steps of your heuristics in general terms (clearly enough that it can be coded). 2) Apply the heuristic to solve the problem in Exercise 5.9, describe how it works on this example step by step. 3) State the result clearly. Which trucks should be used? What is the total cost?

5.9 Modify the heuristics for the 1-BP problem for the case where each bin j,j= 1,,n, has a capacity qj and a cost fj. Apply the modified version of the BFD algorithm to the following problem. Brocard is a road carrier operating Table 5.23 List of the parcels to load and corresponding weight (in kilograms) in the Brocard problem. mainly in France and in the Benelux. The vehicle fleet comprises 14 vans of capacity equal to 800kg and 22 vans of capacity equal to 500kg. The company has to deliver on behalf of the EU 34 parcels of different sizes from Paris to Frankfurt (the distance between these cities is 592km ). The characteristics of the parcels are reported in Table 5.13. As only five company-owned vans (all having capacity of 800kg ) will be available on the day of the delivery, Brocard has decided to hire additional vehicles from a third-party company. The following additional vehicles will be available: - two trucks with a capacity of 3 tons each, whose hiring total cost (inclusive of drivers) is 1.4 per kilometre: - one truck with trailer, with a capacity of 3.5 tons, whose hiring total cost (inclusive of drivers) is 1.6 per kilometre. Which trucks should Brocard hire