Question

1. Bin packing, or some variation of bin packing, can be found in different applications. Use two examples, berth allocation and VRP, to discuss why in some scenarios, these two problems are actually equivalent to bin packing.

Answer 1

A Thumbs Up! Would be really helpful for me. If you have any questions, please leave a comment and I will get back to you as soon as possible.

In the bin packing problem, the items of different volumes are packed in a definite volume of the container in a way that minimizes the number of containers used. Berth allocation problem which is also known as berth scheduling problem is an NP-complete problem considering the allotment of berth space for the vessels. Vessels came from time to time and the operator needs to manage the berths and the loading and unloading of the container as soon as they arrive. The decision problem, where we decide of the item will fit into the bin or not, is NP-complete. There are many varieties of this problem like two-dimensional packing, packing by price, packing by weight, etc.

VRP is a vehicle routing problem combinatorial optimization and programming problem. It deals with a suitable set of routes for vehicles to work in a manner so that the products are to be delivered to a set of customers. The main problem fall in this category is the size problem. This problem is also known as the traveling salesman problem. The main motive of VRP is to reduce the total cost of traveling. The optimal solution to VRP is NP-hard. By computational programming, the problem can be solved.