## 3 Materials and Methods
### Application of PSO and DE to the Postman Delivery Routing Problem
#### 3.3.3 Solution Representation  
In order to apply PSO and DE for solving a combinatorial problem like the postman delivery routing problem, solution representation or solution mapping was required to transform the real number of the \(D\)-dimensional space into practical solutions for vehicle routing. Figure 3 presents the procedure of solution representation with the encoding and decoding scheme. The encoding process aimed to represent a solution as a string of dimensions. In this study, the postman delivery routing problem with \(n-1\) customers (noting that \(n\) is the number of locations, including the post office) and \(m\) vehicles was encoded as a string of \(D\) dimensions. The number of dimensions (\(D\)) was set to be equal to the total number of customers, and the dimension index stood for the customer index. Each value in a dimension was initially filled with a uniform random number in the range [0, 1]. Next, the process of decoding was divided into two stages: (1) the assignment of customers to vehicles and (2) the sequencing or routing for each vehicle. In the assignment stage,  
Figure 2: Evolutionary procedure of the differential evolution (DE) algorithm. the range (max-min) of the dimension value was split by the number of vehicles as in Equation (9):  
\[\text{Split}=(Max-Min)/m \tag{9}\]  
where \(m\) is the number of vehicles, \(Min\) is the minimum value in the dimensions and \(Max\) is the maximum value in the dimensions. According to Equation (9), the range of the dimension value was equally partitioned into \(m\) subsections corresponding to \(m\) vehicles. The span of each subsection is determined in Figure 4. It is noted that a subsection index denoted a vehicle index. Then, a customer was assigned to a vehicle, considering its customer dimension value with the corresponding subsection. For example, if the dimension value of customer 1 fell into Section 2, that customer was assigned to vehicle 2 correspondingly. This process continued until all customers were considered. Once the assignment of customers to vehicles was decided, a heuristic called the nearest-neighbor search (NNS) was applied  
Figure 4: The span of \(m\) subsections. Figure 3: Solution representation procedures. to determine the delivery routing of each vehicle. Thus, for each vehicle, the next visited customer was the one with the nearest distance to the current location. The completed route of a vehicle was obtained when all customers assigned to that vehicle were considered. It is noted that all vehicles needed to depart from and return to the post office. To illustrate the process of solution representation, let us consider an example of the postman delivery routing problem with six customers and two vehicles. A distance matrix between the post office and customers is shown in Figure 5. The sample matrix in this example is symmetric; however, a matrix constructed from the actual operation might be asymmetric, depending on the locations where the delivery process takes place. In the encoding process, the number of dimensions was set to six, which was equal to the number of customers. Each value in a dimension was initially generated with a uniform random number between 0 and 1, as shown in Figure 6.  
Figure 7 illustrates the decoding procedure for obtaining the routing of a vehicle. First, according to Equation (9), the range of the dimension value is divided by the number of vehicles, which is \((0.87-0.25)/2=0.31\). In this example, two subsections are obtained according to the number of vehicles. Then, the condition of the customer assignment is set. The span of sections 1 and 2 are \((0.25,\,0.56)\) and \((0.56,\,0.87)\), respectively. When the customer dimension value falls into the first subsection, that customer is assigned to vehicle 1; otherwise, they are assigned to vehicle 2. Thus, customers 1, 2, 4 and 6 are assigned to vehicle 1, and customers 3 and 5 are assigned to vehicle 2. After that, the routing of each vehicle is determined using NNS method.