Solving NP-Complete Problems by Harmony Search - Music-Inspired Harmony Search Algorithm: Theory and Applications - page 57

Fig. 3. Map of 27 cities in eastern part of China

The HS model [9] was developed to address this problem and compared with the arti-
ficial neural network model [7]. Here, the distance limit equals to 5,000 km. Compared
to the results of ANN, HS could find better solutions three times out of five cases.

5 Vehicle Routing Problem

The vehicle routing problem (VRP) is a combinatorial optimization problem seeking
to pick up, deliver or simply give a service to customers dispersed in an area with a
fleet of vehicles. Each vehicle has a certain capacity and each customer has a certain
demand. Further, there exist a depot(s) and a distance (length, cost, time) matrix
among customers. In VRP, we look for optimal vehicle routes (minimum distance or
number of vehicles). The school bus routing problem (SBRP) is a special case of
VRP. From a school's perspective, the SBRP aims to provide students with an effi-
cient and equitable transportation service.
An example of a network to be optimized consisting of one bus depot, one school,
and ten bus stops is shown in Figure 4. Each bus stop is demanded by certain number
of commuting students, and travel time (in minutes) between two stops is specified on
the link. The objective of the problem is to minimize both the total number of operat-
ing buses and the moving time of the buses.
The HS algorithm could find the global optimum ($307,980) only after 1,000 im-
provisations (or function evaluations), which was examined by the total enumeration
for this

10 6

combinatorial problem [10]. It took 6.6 seconds on Intel
233MHz CPU to search 0.1% of total solution space

4 ( ≈ 1 . 05 × 10 )

3 6

.
HS results were also examined by comparing them with those of GA. In order to
fairly compare HS with GA, the number of objective function evaluations and the

( = 10 / 1 . 05 × 10 )