Rinaldi is an Italian fast carrier located in Parma, whose core business is the transport of small-sized and high-valued refrigerated goods (such as chemical reagents used by hospitals and laboratories). Goods are picked up from manufacturers' warehouses by small vans and carried to the nearest transport terminal operated by the carrier. These goods are packed onto pallets and transported to destination terminals by means of large trucks. The merchandise is then unloaded and delivered to customers by small vans (usually the same vans employed for pickup).

In order to make capital investment in equipment as low as possible, Rinaldi makes use of one-way rentals of trucks. Recently, the company has decided to enter the fast parcel transport market by opening four terminals in the cities of Bologna, Genoa, Padua and Milan.

This choice made necessary a complete revision of the service network. The decision was complicated by the need to transport the refrigerated goods by special vehicles equipped with refrigerators, while parcels can be transported by any vehicle. The forecasted daily average demand of the two kinds of products in the next semester is reported in Tables 1 and 2.

Between each pair of terminals, the company can operate one or more lines. Vehicles are of two types:
• trucks with refrigerated compartments, having a capacity of 12 pallets and a cost (inclusive of all charges) of € 0.4/km;
• trucks with room temperature compartments, having a capacity of 18 pallets and a cost (inclusive of all charges) of € 0.5/km.

In addition, the company considers the possibility of transporting goods at room temperature through another carrier, by paying ¤ 0.1/km for each pallet. A directed graph representation of the problem is given in Figure. Distances between terminals are reported in Table 3.

Formulate the LFCND problem of finding the least-cost service network (hint: |K| = 22 commodities, one for each combination of an origin-destination pair with positive demand and a kind of product). Apply the drop heuristic to find a feasible solution of the problem.

By using a solver, determine the optimal solution of the problem and the costs corresponding to the weak and the strong continuous relaxations. What is the quality of the feasible solution provided by the drop heuristic and the two lower bounds?