Some Studies on the Principles and Mechanisms for Loading and Unloading

Rail mounted gantry cranes are widely used in container loading and unloading. It is built in the form of a bridge, supported by a trestle at each end. Its fixed horizontal boom projects over trains being loaded or unloaded. Therefore RMGC works on the offside of the containers being loaded/ unloaded at the rail siding and position them in a way so as to be visible to the crane operator. For more technical information about RMGC used in CONCOR see Appendix B. To unload a train the RMGC as shown in Figure ý3. picks up the containers from the train and put them on shuttle trucks that move them to the storage yard in the terminal. To load trains the RMGC unload containers from shuttle trucks and put them on the train.

Figure ý3. Rail mounted gantry crane

A reach stacker is used to load unload container to/from trains. It has more flexibility to move inside the terminal. There are several reach stackers that are being used in ICD, Tughlakabad to load/unload containers, out of which four are owned by the CONCOR while the rest are owned by different agencies.

Figure ý3. Truck used for transhipment of containers

Trucks as shown in Figure ý3. are used for transhipment of containers. Each truck has its own identity number and performs its task according to the available container to be loaded and unloaded.

Storage yard operation

In storage yard, the yard is divided into three parts. The first part is the main storage area where shuttle trucks move containers from/to the rail side. The storage area has 5 blocks, and each block contains 7 rows and 72 columns except the first and the last blocks which contain 4 rows and 72 columns, and 7 rows 70 columns respectively. TMGC serve the main storage yard area as shown in Figure ý3.. Technical information of TMGC are given in Appendix B. Containers can be loaded unloaded reshuffled, and staked on the top each other up to 5 storey high. There are some constraints which impose a sequence to be repeated in storing containers (e.g. size, weight, port of distinction, series of distinctive characteristics such as hazard class and the kind of goods transported).

Figure ý3. Part of storage yard in CONCOR served with TMGC.

The second part consists of storage area for empty containers. It is divided into four blocks each block consist of 5 rows and 25 columns, except the first block which consists of 4 rows 6 columns. This part is serviced by reach stackers which can stack containers to 4 storey high. The third part is used for temporary storage of containers whenever necessary.

To enable online availability of data pertaining to container stacking, CONCOR has installed a Management Information System (MIS) at ICD, Tughlakabad. As soon as there is any change in the stack position, it is instantly fed to the computer server by a Radio Data Terminal operated by the operational task force.

Gate operation

At the gate of ICD, Tughlakabad, checking of all in and out containers and trucks is done by a designated clerk. All the reservations and paperwork are checked at the “gatehouse” which is a structure at the gate where the clerk inspects and clears the entrance and exit of all containers and trucks.

Summary of operations at ICD, Tughlakabad

The entire operations at ICD have been further divided into micro operations. Analysis of control, operation and scheduling of container handling operations can be summarized in Table ý3.. It can be seen that except container stock and booking position, none of the operations are scheduled or planned using the real time planning of logistics.

Table ý3. Summary of loading/unloading operations at ICD, Tughlakabad

ActivitiesMethod of control/ operation/ schedulingArrival /Departure of container trainInformation submitted by communication systemArrival/ departure of container carrier (input/ exit of container)Information transmitted by communication system

Unloading activity Manually scheduled

Unloading from container train by gantry cranesManually scheduled, crane operation

Placing over the shuttle truckCrane operationMovement of shuttle truck to stack positionShuttle truck operationDirection to the shuttle truck operator to transfer the container to stack positionManual indication to the shuttle truck operator

Unloading of the container from the shuttle truck to placing on the stackReach stacker operation, directed by information from MIS

Any mid course instruction to the truck driverDelivered manually alone

Loading activity (nearly same as for the unloading)Nearly same as for unloading

Stock inventory position of containersAvailable on MIS

Requirement of movement of a particular container Available on MIS

Availability position of empty containerAvailable on MIS

Custom position of a container pertaining to export/ import Container delivery requirement of clientAvailable on MIS

Container booking position for onward transport

Available on MIS

Survey and data updatingGate in / Gate Out of containers / trucks at ICD,TKD

Rail in / Rail out of containers at ICDITKD

Internal shifting within the yard

Mathematical Model Formulation

Introduction

This case study for this work is the inland container terminal (ICD) at Tughlakabad in New Delhi. ICD, Tughlakabad is a dry port served by trains. The terminal consists of a rail-side area where trains arrive, get serviced, loaded, unloaded and depart from the terminal. There is a yard area, where containers are stored until they are transported to their destination. The terminal handles a number of trains, and each train is served by variety of equipments that load and unload containers onto and from trains. Similarly, there are a number of yard cranes in the yard-side that load and unload containers onto and from trucks. Most containers handled by the terminal are of standard sizes (e.g. Table ý1.) and the containers are transported in the terminal area using a fleet of trucks of unit carrying-capacity, each truck can transport only one container at a time. With the use of MIS, the location of each container in the terminal can be tracked.

Problem description

Typically, there are large numbers of containers to be loaded onto or unloaded from Trains everyday in a terminal. On an average, 7-8 trains arrive to the terminal everyday to unload 500- 600 containers. The containers are then required to be loaded to transport them to their destination. Throughout the container handling operation, trucks, RTMG and YCs need to be available to ensure a continuous container flow. A truck that finds the RMGC/TMGC at its job location busy with handling containers for other trucks will join the rail-side crane queue and wait until the crane becomes available to serve it. Similarly, a RMGC/TMGC that does not find a truck assigned with a job parking under it will be idle until a truck arrives with a service request.

In order to reduce terminal turnaround times, it is of utmost importance to ensure an efficient and effective transportation of containers between the rail-side and the yard-side using a fleet of trucks. A gain in terminal productivity cannot be necessarily achieved by increasing the number or the speed of trucks operating in the terminal. This is because the possibility of congestions in the terminal increases with the number of trucks operating at higher speeds. At the same time, if less number of trucks are used then it would results in idle cranes. Therefore, an efficient and effective scheduling mechanism is needed to schedule containers on trucks using some principles to minimize unnecessary truck waiting times and cutting down capital investment and operating costs. This can be efficiently achieved by minimizing the makespan. Similar scheduling problems in container terminals have been analyzed by various researchers (for example, Bish et al. 2001; Li et al. 2004; and Nishimura et al. 2005). These researchers focused on a class of truck dispatching rules called the vessel-based truck dispatching policy in which a fleet of trucks is usually assigned to a specific vessel until their work is completed.

One major issue in terminal planning is how to determine the sequence of containers to be handled on a fleet of trucks. This sequencing decision affects the operation efficiency of both the rail-side and the yard-side to a large extent .Unnecessary truck waiting time would lead to a longer terminal turnaround time. .A few hours before arrival of an incoming trains the terminal receives detailed information about their contents; i.e., containers that are to be unloaded into the yard, as well as the list of containers currently in the yard that should be uploaded onto the trains. This information allows the terminal dispatchers to generate so-called container sequence.

It is no surprise that managing, controlling and operating such system is a very complex phenomenon. At the operational level the question is how trucks con be routed in this complex system, in which mechanism should trucks be dispatched to containers, and what is an effective traffic control mechanism? Similarly, at the strategic level, the issues include optimizing the number of cranes, trucks etc. The truck dispatching problem can be considered similar to the job scheduling problem on parallel machines. In a truck dispatching problem, the crane operations represent the setups, crane represents the operator, each container corresponds to job and trucks correspond to machines. However, the job scheduling problem for container terminals has not been studied in the literature. Therefore, this study aims to develop models for effective and efficient loading and unloading operations for ICD, Tughlakabad in New Delhi.

Truck dispatching model formulation

This section describes the formulation of mathematical model for the truck dispatching problem by considering one or more number of trains serviced with a single crane. Let R number of trains to be serviced with a K number of trucks using a single crane. The number of trains to be considered in the model depends upon the availability of trains in the terminal. The container loading and loading problem with a single crane can be formally described as follows: we would like to minimize the time required to execute a given set of unloading containers in a predetermined sequence, followed by a given set of loading containers in a predetermined sequence. The execution time of every job is deterministically known and consists of two components: (i) the time required for the rail side crane to pick/drop a container from/onto a truck (during this time both the crane and the truck are occupied); and (ii) the time required to transport the container between the crane and the appropriate yard location. Upon completing the last unloading job assigned to truck, the truck transfers directly to the first loading job assigned to it (if any) without passing through the crane. Since the loading and unloading sequences of the jobs are given, the decision problem is to assign the loading and unloading jobs to trucks so as to minimize the makespan of the schedule. The formulation of truck dispatching problem as a mixed-integer program is presented below.

Parameters

N number of jobs

M number of trucks available (Nµ §M)

µ § Processing time, where i=1,2,...,N.

µ § half travel time where i=1,2,...,N.

µ §arrival time(completion time of job i) where i=1,2...,N.

µ § departure time of job i, where i=1,2...,N.

K large positive number

Decisions Variables

µ §is a binary variable number whose value is 1 if truck m (m=1,2,....,M) handles job j after job i (i=1,2,...,N), otherwise it is zero.

µ § is a binary variable whose value is 1 if truck m (m=1,2,...,M) handles job i (i=1,2,...,N) otherwise it is zero

T is the makespan for N Jobs.

Denoting the set of µ §by X, the set of µ § by Y, and the set µ §of by t, the truck dispatching can be stated as follows

Minimize T

Subject to

µ § i=1, 2...,N Eq ý4.µ §=1 i=1, 2 ...,NEq ý4.µ § Eq ý4.µ § Eq ý4.µ §

i, j=1,2,¡K,N and i‚ j , m=1,2,...,MEq ý4.µ §

i, j=1,2,...,N ; i‚j ; m=1,2,...,MEq ý4.µ § , i=1, 2 ...,NEq ý4.µ § j=1, 2 ...,MEq ý4.µ §

µ § Eq ý4.µ § i=1,2,...,N; j=1,2,...N+1; m=1,2,...,MEq ý4.µ § i=1,2,...,NEq ý4.The objective in the truck dispatching problem is to minimize the makespan of the N jobs. Constraint (4.1) states the relationship between the arrival times and the makespan. Constraints (4.2) ensure that each job is handled by only one truck. Constraints (4.3) to (4-5) give the relationship between X and Y for jobs handled by the same truck. Constraint (4.3) ensure thatµ § must be equal to 1 if truck m handles a job after job i. Constraints (4.4) ensure that µ § must be equal to 1 if truck m handles a job before job i. Constraint (4.5) ensure that if µ §equals 2, truck m handles either job i before job j or job j before job i. Constraint (4.6) gives the relationship between the completion time of a job and that of its successor job i completes before job j. Constraint (4.7) states the relationship between a job’s completion time, travel time, and departure time of job i. Constraints (4.8) give the initial scheduling of M number of jobs to M Number of trucks . Constraints (4.9) describes the second assignments of i-m jobs to M number of trucks .constraints (4.10) and (4.11) are simple constraint to ensure that X, Y, and t are non-negative.

In typical container terminals such as ICD, Tughlakabad, trucks travel at the speed of 15 km/h in the terminal area. The layout of the terminal is shown in Figure ý4.. The respective times taken by a RMGC and TMGC to handle a container are 1.5 minutes and 5 minutes. All the locations of containers are uniquely identified by the (x, y) coordinates with respect to a defined origin. The initial location of each truck is next to RMGC so that it is ready to be loaded with containers for transhipment to its predefined location in the storage yard area. The travel time of each container is the distance covered divided by the speed of the truck. The duration of a loading or unloading time of a container is equal to the sum of the travel time and the total crane handling time plus waiting time, if any. A terminal operations control system is typically used to determine the container ready time and truck ready time.

Solution of truck dispatching problem

A real-world problem of dispatching 2 trucks to transport 5 containers is solved with the objective to minimize the makespan of the operation. The values of input data µ § of the problem are given in Table ý4.. The problem is formulated and solved using the AMPL software (AMPL, 2009) for the input data given in Table ý4.. Using the mixed integer programming model, the makespan for the problem was found to be 23 minutes. Table ý4. gives the truck schedule of problem, including the container departure timeµ § and the completion time of each container on each truck.

Table ý4. Input data for truck dispatching problem

Container Number iTravel time, 2di (minutes)Processing Time, s

(minutes)13225 232.5244252 2Table ý4. Output from MIP model

Container NumberDeparture time µ § MinutesCompletion time of the jobs (makespan) µ § minutesTruck number128124142310151416232517211

Figure ý4.Layout of ICD, Tughlakabad

Several computational experiments were conducted for various combinations of number of trucks and containers. For each combination, the solutions were obtained using AMPL on a personal computer with 2.10 GHz CPU. It was found from the computational results that even for these problems, the average computational time required to find the optimal schedule is about few minutes while for large problem the computational time required is over 3 hours, Table ý4. shows the computational time for different combinations of number of trucks and number of containers.

Table ý4. Computational time requirements for combinations of number of trucks and containers

NO.Number of TrucksNumber of containersComputational time12516 Minutes23923 minutes341531 Minutes451842 Minutes

The results of the computational analysis carried out in this chapter clearly indicate that AMPL is capable of finding optimal schedule for large container unloading and loading problem. However, the computational time required for solving large problems is quite high. In view of large computational time, application to AMPL to solving real-life terminal operation problems is not practical. Therefore, a heuristic algorithm is proposed in the following chapter to solve the truck dispatching problem.

Solution Mechanisms

Introduction

This chapter describes mechanisms for scheduling a number of containers on a number of trucks. In such mechanisms, trucks are the players of the mechanism. According to Noam Nisan (2007), mechanism is a special class of algorithm. According to Heydenreich et al. (2008), a scheduling mechanism is a scheduling algorithm on an operating system. A flowchart of the solution mechanism is shown in Figure ý5.

Figure ý5. Flow chart of scheduling mechanism

From the flowchart shown in Figure ý5., the mechanism can be done by applying scheduling algorithm on operating system through number of principles. to get the makespan, then finding out the minimum makespan followed by finding number of trucks , operation cost, and waiting time corresponding to the minimum makespan The problem of obtaining scheduling mechanism through different algorithms to get an optimal solution is not new. Many researchers including Gillett et al. (1974), Aarup et al. (1994), and Zeng et al. (2009 ) have studied the similar problem.

Greedy algorithm

One of the first applications of greedy algorithm (GA) to computational optimization problem was reported by Edmonds (1971). Greedy algorithms are simple and straightforward. They are short-sighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Greedy algorithms are used to solve optimization problems (for example Kleinberg et al. 2005, and Khuller et al. 2007). GA has been applied to wide variety of disciplines ranging from stock portfolio management to choosing a University. GA is easy to code, easy to debug, executes quickly, and is robust. GA has been applied to a wide variety of problems from several fields of science, technology, and management.

Elements of a GA

An optimization problem involves finding a subset, µ §from a collection of candidatesµ §; the subset, µ §, must satisfy some specified criteria, i.e. be a solution and be such that the objective function is optimised by µ §. `Optimised' may mean maximized or minimized, depending on the precise problem being solved. Greedy methods are distinguished by the fact that the selection function assigns a numerical value to each candidate. All GA’s have exactly the same general form. A GA for a particular problem is specified by describing the predicates `solution' and `feasible'; and the selection function `select'.

Consequently, GAs are often very easy to design for optimization problems.

The General Form of a Greedy Algorithm is

function select ( µ §: candidate_set) return candidate;

function solution (µ § : candidate_set) return

boolean;

function feasible (µ § : candidate_set) return

boolean;

***************************************************

function greedy (C : candidate_set) return candidate_set is

µ § : candidate;

µ § : candidate_set;

begin

µ § := {};

while (not solution(µ §)) and µ § /= {} loop

µ §:= select(µ §);

µ § := µ § - {µ § };

if feasible(µ §union {µ § } ) then

µ §:= µ §union { µ §};

end if;

end loop;

if solution(µ §) then

returnµ §;

else

return eµ §;

end if;

end greedy;

One useful concept for proving the correctness of greedy algorithms is the definition of a promising set ,that is a feasible set is promising if it can be extended to produce not merely a solution but an optimal solution to the problem . It follows that:

Lemma. If µ § is promising at every step of the Greedy procedure and the procedure returns a solution, then the solution is optimal

The working principle of a GA can be understood with the help of an example. Consider that it is required to count a certain of money using the fewest possible number of bills. Assume that the following bills are available: Rs. 50, Rs. 20, Rs. 10, Rs. 5 coin, Rs. 1 coin, and 50 paisa coin.

The set µ § of candidates is the collection of coins (1; 2; 5; 10; 20; 50), The feasibility function is that the next coin must not bring the total to more than what is required. The selection function is the value of the coin. The solution function is whether the selected coins reach the desired target. A GA would start the solution process by picking up the largest possible bill or coin that does not overshoot. Suppose, the problem is to count Rs. 79.50. The choices would be:

a Rs. 50 bill

a Rs. 20 bill, to make Rs. 70

a Rs. 5 coin, to make Rs. 75

two Rs. 2 coins, to make Rs. 79

a 50pais coin, to make Rs. 79.50

It is noted that that GA is able to achieve the optimal solution for this problem. However, GA may not be able to achieve an optimal solution for every monetary system. For example, consider a problem where a vending machine needs to return 41 cents to a customer using the available coins of 25-cent, 10-cent, and 1-cent. The GA would start he solution procedure in the following manner.

Pick up a 25-cent coin, to make 25-cent

Pick up a 10-cent coin, to make 35-cent

Pick up six 1-cent coins, to make 41-cent

It can be seen that although the GA was able to achieve the solution but it is not an optimal one. The total number of coins as determined by GA is 7 while it is a possible to achieve a better solution that requires only 5 coins. The optimal solution, can, therefore, be achieved using four 10-cent coins and one 1-cent coin.

Types of GA

Greedy algorithms are equally applicable to simple problems such as the money change problems as discussed above to large complex problems that are difficult to solve using classical techniques. GA can be effectively used as a selection algorithm to prioritize options within a search, or branch and bound algorithm. GA is sometimes characterized as being 'short sighted', and as 'non-recoverable'. However, if a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it executes faster than other optimization methods like dynamic programming. Examples of such GA’s are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, Dijkstra's algorithm for finding single-source shortest paths, and the algorithm for finding optimum Huffman trees (Thomas, 2001)

There exist several versions of greedy algorithm. The four most commonly used are:

Pure Greedy Algorithm

Orthogonal greedy algorithm

Relaxed greedy algorithms

stepwise projection algorithms

Greedy algorithm and scheduling problems

Scheduling problem of set of job on one machine

Suppose we have n jobs and every job i has start and finish time (si, fi). The goal is to schedule the maximum number of non overlapping jobs on a single machine. GA can be applied to this problem by scheduling jobs successively ensuring that no assigned jobs overlap with previously scheduled jobs. The decision problem is to determine the order in which the jobs should be processed so that the scheduling mechanism is optimal. There are several ways to solve this problem. Suppose for example, jobs can be picked in increasing order of size. It is easy to see that this does not necessarily lead to the optimal solution. Likewise, scheduling jobs in order of their arrivals (start times), or in increasing order of the number of conflicts that they have, also does not work. Thus the possible greedy algorithms strategies are as below: