Minimizing the total weighted delivery time in container transportation scheduling

We consider the problem of transporting containers from one port to another using a fleet of ships. Each ship has a capacity constraint that limits the total number of containers it can carry; each ship calls on a specific set of ports that is referred to as its route and each ship follows a fixed route with a fixed departure time at each port. Each container has a release date, that is, the date when it becomes available for shipping at its origination port; it cannot be loaded onto a ship before its release date. Also, each container has an importance factor referred to as its weight. The delivery time of a container is defined as the time when the container is delivered by a ship at its destination port. We consider the problem of minimizing the total weighted delivery times over all containers. We consider three scenarios with regard to the routes of the ships, namely, (i) identical routes, (ii) nested routes, and (iii) arbitrary routes. We determine the computational complexity of the problems and provide heuristics with their worst-case analyses.