by Malay Bhattacharyya
Abstract
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.

i i s f

Introduction

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.

c i i

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.