by Malay Bhattacharyya
Courier problems comprise a set of recently proposed combinatorial optimization problems, which are inspired by some novel requirements in railway wagon scheduling. In these problems, scheduling strategies of some mobile couriers are considered. These mobile couriers initially
reside at some fixed location. They are assigned some duties of commodity transfer between different
pairs of locations. The scenario may be static or dynamic. The motivation is to optimize the movement
of the couriers over the constraint of the traversed path or the associated cost. I discuss here some vari-
eties of the courier problems, formalized on graphs, and address the potential methods of their solution.
Optimization theory is one of the oldest branches of mathematics, finding a myriad of applications in the broad spectrum of scientific and engineering disciplines [ 1]. Many real-life problems can be formalized as an
optimization problem. Even a simple problem that might arise to a fashion designer, like finding an optimal matching of tooth colors, easily finds
its optimization counterpart [ 7]. The objective in an optimization problem is to maximize or minimize a given function f (x). The nature of this
function, known as the objective function, can be in any arbitrary form,
e.g., univariate or multivariate, low-dimensional or high-dimensional, and
so on. In single and multiple objective problems, the characteristics of the
optimization function are very important. The benchmark functions to
evaluate an optimization method are often guided by these features [ 8].
I discuss some of these characteristics of functions below.
Polynomial Function: A function given in the form f (x) = anxn +
an–1xn– 1 + … + a1x + a0 , where a0 , a1,…, an are constants and n is a
nonnegative integer, is known as a polynomial function of order n.
When n = 1, 2, 3, 4, 5, ... the function f (x) is said to be linear, quadratic, cubic, quartic, quintic, and so on, respectively; e.g., f (x) = 2 x2
+ 1 is a quadratic function.
Continuous Function: A function f (x) is said to be continuous if
or all the points a in its domain, Ltx→a+ f (x) = Ltx→a– f (x) = f (a). In
case this relation desatisfies for any point in the domain of the function f (x), it is said to be discontinuous. The function f (x) = sin2x is a
continuous function. A function is discrete if for none of the points
in its domain it is continuous; e.g., f (x) = |¯x¯|, denoting the smallest
integer greater than or equal to x, is a discrete function.
Unimodal Function: A function f (x) between two ordered sets is
aid to be unimodal if for some arbitrary m (the mode), it monotonically increases for x ≤ m and monotonically decreases for x ≥ m, and
f (x) attains the only maximum value at m without attaining any other
local maxima. If f (x) has multiple such modes, then it is said to be a
multimodal function. The function f (x) = 10 x is a unimodal function.
Convex Function: A real-valued function f (x) defined on an
nterval is called convex if for any two points x and y in its domain L
and for any t ; [0, 1], f (tx + ( 1 – t)y) ≤ tf (x) + ( 1 − t)f ( y). In other
words, if f ;(x) ≥ 0, for all x, then f (x) is said to be convex. A function
is strictly convex when the said above equality relations do not hold;
e.g., f (x) = |x|p for p ≥ 1 is a convex function.
Concave Function: A real-valued function f (x) defined on an
nterval is called concave if for any two points x and y in its domain
L and for any t ; [0, 1], f (tx + ( 1 – t)y) ≥ tf (x) + ( 1 − t)f ( y). In other
words, if f ;(x) ≤ 0, for all x, then f (x) is said to be concave. A function
is strictly concave when the said above equality relations do not hold;
e.g., f (x) = – x2 is a concave function.
Deterministic Function: A function is said to be deterministic if
t always returns the same result as output for a specific set of input
values. In contrast, if a function associates a noise term (generally additive), i.e., returns different values for the same input, it is called a stochastic function. The function f (x) = log x is a deterministic function.
Differentiable Function: A function f (x) defined on an open
nterval is called differentiable if for any point a within the interval,
the value of Lth→0( f (a + h) – f (a))/h exists. Otherwise, f (x) is nondifferentiable. The function f (x) = tan– 1 is a differentiable function.
Optimization problems having a pronounced discrete or combinatorial structure are known as combinatorial optimization problems. Many real-life problems have a combinatorial nature. I address
here a new class of combinatorial optimization problems, which are
known as Courier Problems (CP). These are motivated by the com-plexities involved in the problem of transportation scheduling [ 6, 9].
Consider a system consisting of a set of locations and some mobile
ouriers initially residing at one of these locations. There exists a set
of pairs of locations between which commodity transfer is required.
These transfers of commodities involve costs that are proportional to
the path distances between the corresponding pair of locations. The
courier selects a pair and reaches its source location. It then collects
the commodity, moves to the destination, and delivers the commodity. Again, it selects the next pair, moves to the source of the pair, and
Figure 1: Scenario of a courier problem.