Information Technology Reference
In-Depth Information
optimization algorithm. In this section, some of these problems are explained and
their objective functions are formulated. The knapsack problem, travelling salesman
problem (TSP), drilling location and hit sequencing, dynamic pick and place (DPP)
model in robotic environment, vehicle routing problem (VRP), and facility layout prob-
lem, which are examples of strict-sense combinatorial problems, are discussed in this
sub-section.
2.2.1
Knapsack Problem
For example, the single constraint (bounded) knapsack problem reflects the dilemma
faced by a hiker who wants to pack as many valuable items in his or her knapsack as
possible without exceeding the maximum weight he or she can carry. In the knapsack
problem, each item has a weight, w j , and a value, c j (Equation 2.1); the constraints are
in (Equation 2.1). The goal is to maximize the value of items packed without exceeding
the maximum weight, b. The term represents the number of items with weight w j and
value, c j :
maximize:
D
1
j =0 c j x j ,
x j
0 , integers
(2.1)
subject to:
D
1
j =0 w j x j b ,
w j
0 , b > 0 .
(2.2)
The solution to this problem will be a set of integers that indicate how many items of
each type should be packed. As such, the knapsack problem is a strict-sense combinato-
rial problem because its parameters are discrete, solutions are constrained and it has no
continuous counterpart (only a whole number of items can be placed in the knapsack).
2.2.2 Travelling Salesman Problem (TSP)
In the TSP, a salesman must visit each city in his designated area and then return home.
In our case, the worker (tool) must perform each job and then return to the starting con-
dition. The problem can be visualised on a graph. Each city (job) becomes a node. Arc
lengths correspond to the distance between the attached cities (job changeover times).
The salesman wants to find the shortest tour of the graph. A tour is a complete cycle.
Starting at a home city, each city must be visited exactly one time before returning
home. Each leg of the tour travels on an arc between two cities. The length of the tour
is the sum of the lengths of the arcs selected. Fig 2.1 illustrates a five-city TSP. Trip
lengths are shown on the arcs in Fig 2.1, the distance from city i to j is denoted by c ij .
We have assumed in the figure that all paths (arcs) are bi-directional. If arc lengths dif-
fer depending on the direction of the arc the TSP-formulation is said to be asymmetric,
otherwise it is symmetric. A possible tour is shown in Fig 2.2. The cost of this tour is
c12 + c24 + c43 + c35 + c51.
Several mathematical formulations exist for the TSP. One approach is to let x ij be 1
if city j is visited immediately after i , and be 0 if otherwise. A formal statement of TSP
is given as follows:
Search WWH ::




Custom Search