Crossroads - Summer 2009

f continues the same routine until the set of source-destination pairs is exhausted. This entire activity is termed a round. The life of a courier is defined by a sequence of many such rounds.

In a simple view, the complete scenario may be described by the four inite sets MC, L, LC and SD, where MC denotes a finite set of couriers, L ; L is finite a set of locations, LC is the initial location of the couriers, and SD ; L × L is a set of source destination pairs. I describe one such situation in Fig. 1. Suppose there are two couriers assigned to completing the task of commodity transfer in a disjoint manner. The tuples associated with the situation in Fig. 1 are given below.

• MC = {MC1, MC2},

• L = {A, B, C, D, E},

• LC = A,

• SD = {(A, D), (B, E), (C, F)}.

In this case, the two rounds shown in two different colors (red and blue) in Fig. 1 could describe a possible solution to the problem. In the following sections, similar scenarios are described with formal approach, which could possibly occur in different versions of CP.

Preliminaries of Graph Theory

A simple graph G is defined by the two finite sets V and E. The set V = {v1, v2 ,…, vn} contains the vertices and E = {(i, j )| i ≠ j; i, j ; V } the edges. In Fig. 1, we have V = {A, B, C, D, E} and E = {V × V − {(A, A), (B, B), (C, C), (D, D), (E, E), (F, F)}}. By considering the edges (i, j ) and (j, i) dissimilar, G is assumed to be a directed graph. Here, a function W is defined over the set E, mapping the edges to a real value. According to this function, Wij is the weight associated with the directed edge (i, j ). Thus, G becomes a weighted graph.

A path between two vertices v1 and vn+ 1, denoted as Pv1vn+ 1, in a graph G is an ordered and alternating sequence of distinct vertices and edges [v1 – v2 – … – vn – vn+ 1], such that vi ; V, vi ≠ vj , and (vi , vi+ 1) ; E, ∀ i, j ; { 1, 2,…, n}. The length of this path is the number of edges it contains, i.e., n. The weight of this path Pv1vn+ 1 is given by W (Pv1vn+ 1 ) = ∑i = 1 to n Wvivi+ 1, where Wvivi+ 1 denotes the weight associated with the directed edge (vi , vi+ 1). A subpath is a matching subsequence of vertices and edges of a path. A circuit starting from a vertex v1, denoted as Cv1vn+ 1, is a path beginning and ending with the same vertex v1. The weight of this circuit is given by W (Cv1vn+ 1) = ∑i = 1 to n– 1 Wvivi+ 1 + Wvnv1. A graph G is said to be connected if there is at least one path, having no repetition of vertices, between each vertex pair in G. In this article, the term graph will denote an arbitrary directed and weighted graph that is connected.

The Problems of Couriers

Now I formally discuss the different versions of the courier problems. A courier problem is defined over the 5-tuple (MC, L, LC, SD, W ), where MC denotes a finite set of couriers, L ; L is a finite set of locations, LC is the initial location of the couriers, SD ; L × L is a set of source destination pairs, and W is a cost function associated with the location pairs. For the single courier problems, the tuple MC is a singleton (a set containing a single element). Therefore, it has been omitted from the appropriate cases.

Single Courier-Single Packet Problem: Given a quadruplet (L, LC, SD, W ), find the circuit to be traversed by a courier carrying a sin-

( gle commodity at a time, such that the commodity transfer between the source-destination pairs given in SD are exhaustively covered and the cost of traversal is minimum.

Single Courier-Multiple Packet Problem: Given a quadruplet L, LC, SD, W ), find the circuit to be traversed by a courier, allowed to carry multiple commodities at a time, such that the commodity transfer between the source-destination pairs given in SD are exhaustively covered and the cost of traversal is minimum.

Multiple Courier-Single Packet Problem: Given a 5-tuple (MC, L, LC, SD, W ), find the |MC| (the number of couriers in MC) disjoint circuits to be traversed by the couriers carrying a single commodity at a time, such that the commodity transfer between the source-destination pairs given in SD are exhaustively covered and the total cost of traversal of all the couriers is minimum.

Multiple Courier-Multiple Packet Problem: Given a 5-tuple MC, L, LC, SD, W ), find the |MC| (the number of couriers in MC) disjoint circuits to be traversed by the couriers, allowed to carry multiple commodities at a time, such that the commodity transfer between the source-destination pairs given in SD are exhaustively covered and the total cost of traversal of all the couriers is minimum.

(

Similarly, the dynamic versions are defined on a dynamic envi-onment, where the positions of the locations are changing over time. As a result, the function W, defining the cost of traversal between location pairs, also gets changed. Different versions of such transportation problems were first introduced in [ 3]. These problems are shown in hierarchical form in Fig. 2.

Figure 2: The problem tree of the couriers.

Approach to Solution

To date, a simplified static version of CP, concerning a single mobile courier, has only been addressed in literature [ 4]. It describes the first heuristic solution method of a simpler version of the single courier problem. In terminology, the problem is known as the single courier-single packet static problem or SC–SP2. In brief, the problem concerns finding the route, which starts from and ends at a fixed base location amongst a given set of static locations, without repetition, for which the cost of traversal will be the minimum one. For the clarity of the solution, sometimes these problems are mapped on a graph. I also address it by mapping on a graph and, finally, to the well-known traveling salesman problem (TSP). The mapping of a single courier-single packet static problem to an equivalent graph is performed by the following rule.