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 heuristic to the following problem. Brocard is a road carrier mainly operating in France and Benelux.
The vehicle fleet is composed of 14 vans of capacity equal to 800 kilograms and 22 vans of capacity equal to 500 kilograms. The company has to deliver 34 parcels of different sizes from Paris to Frankfurt (the distance between these cities is 592 kilometres). The characteristics of the parcels are reported in Table.
As only five company-owned vans (all having a capacity of 800 kilograms) 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 three 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?
| Table : List of the parcels to be loaded and corresponding weight (in kilograms) in the Brocard problem. |
|
Parcel
|
Weight
|
Parcel
|
Weight
|
|
1
|
228
|
18
|
170
|
|
2
|
228
|
19
|
170
|
|
3
|
228
|
20
|
170
|
|
4
|
217
|
21
|
170
|
|
5
|
217
|
22
|
95
|
|
6
|
217
|
23
|
95
|
|
7
|
217
|
24
|
95
|
|
8
|
210
|
25
|
95
|
|
9
|
210
|
26
|
75
|
|
10
|
210
|
27
|
75
|
|
11
|
210
|
28
|
75
|
|
12
|
195
|
29
|
75
|
|
13
|
195
|
30
|
75
|
|
14
|
195
|
31
|
75
|
|
15
|
170
|
32
|
55
|
|
16
|
170
|
33
|
55
|
|
17
|
170
|
34
|
55
|