Tanker Scheduling Project

Problem Description

A transportation company uses its boats to ship perishable goods among different cities located in the Pacific coast. Since the cargo is perishable, the customers are concerned about delivery times. The cargo should reach the destination not later than the required delivery date. The company wants to determine the minimum number of ships needed to meet required delivery dates. In modeling and solving this problem, one should consider the time it takes to load/unload a shipment and the time it takes to reach the next destination port.

The aim of this project is to build a decision support system that enables the user to identify the total number of boats needed to meet the required delivery times. Below we present a network flow formulation of this problem.

Network Flow Model

The tanker-scheduling problem can be formulated as a network flow problem. The corresponding network contains a node for each shipment and an arc from node i to node j if it is possible to deliver shipment j after completing shipment i; that is, the start time of shipment j is no earlier than the delivery time of shipment i plus the corresponding unload time and travel time from the destination of shipment i to the origin of shipment j. We split each node i into two nodes i’ and i” and add the arc (i’, i”). Set a lower bound for each shipment arc (i’, i”) to 1. Add a source node s in this network that is connected to the origin of each shipment i’, and add a sink node t that is connected to each destination node i”. Set the capacity of each arc in the network equal to 1. In this network each directed path from source s to sink t corresponds to a feasible schedule for a single ship. As a result, a feasible flow of value v in this network decomposes into schedules of v boats; and our problem reduces to identifying a feasible flow of minimum value. Note that the zero flow is not feasible because shipment arcs have lower bounds equal to 1 unit.

The following notation is used:

v presents the number of boats needed

A presents the set of arcs in the network

A* presents the set of shipment arcs (i’, i”) of the network

N presents the set of the nodes in the network.

The decision variables are as follows:

xij takes value 1 if arc (i,j) is used and 0 otherwise.

Augmenting Path Algorithm

The following is an algorithm that can be used to solve the tanker-scheduling problem. To learn more about network flow problems and the augmenting path algorithm, we refer the students to Ahuja et al. (1993).

Let G denote a network with a set N of nodes and a set A of arcs. Network G(x) is called a residual network, and it consists of the arcs with positive residuals. An augmenting path P is a directed path from the source s to sink t in the residual network G(x). We define the residual capacity of an augmented path () as the minimum residual capacity of this path (min {rij: (i,j)P}).

begin

x = 0

while G(x) contains a directed path from node s to node t do

begin

identify an augmenting path P from node s to node t

 = min {rij: (i,j)P}

augment  units of flow along P and update G(x)

end

end

Excel Uygulamalar için Visual Basic

Proje NO: #4417653

Proje hakkında