Project topics and materials
Get Complete Project Material File(s) Now! »
Improving the initial solution heuristic
Initialization criteria in Algorithm 4.1 refer to the process of finding the seed customer: the first customer to be inserted into a new route. Joubert (2003) proposes the use of the TWC concept to identify seed customers. When looking at the TWCM example, it is clear that the incompatibility is distinct for specific nodes. It is therefor possible to identify incompatible nodes. As opposed to the two most common initialization criteria, namely customer with earliest deadline, and furthest customer, as suggested by Dullaert et al. (2001), the author of this thesis proposes the use of the TWCM to identify seed nodes based on their time window compatibility. Table 4.3 indicates the number of instances where a node has an infeasible time window with another node, either as origin, or as destination. Both nodes c1 and c2 have five infeasible instances. The two artificial nodes are representing the same customer c. It can be concluded that customer c is the most incompatible node, and is identified as the seed customer. Ties are broken arbitrarily. Should two nodes have the same number of infeasible time window instances, either of the two customers could be selected as seed customer.
It may be possible to not have any infeasible time window instances. In such a scenario, a total compatibility value, denoted by Ctotal a , can be determined for each node a, and is calculated using either (4.8) or (4.9), where M refers to all the unrouted nodes, including all instances of those nodes that are split artificially. The customer with the lowest total compatibility is selected as seed customer.
Once the seed customer has been identified and inserted, the SIH algorithm considers, for all unrouted nodes, the insertion position that minimizes a weighted average of the additional distance and time needed to include a customer in the current partially constructed route. This second step is referred to as the insertion criteria. Note that the terms nodes and customers are used interchangeably. The insertion and selection criteria can be simplified using the example illustrated in Figure 4.7. The partially constructed route in the example consists of the depot and three routed nodes, namely B, C, and E.
Initial solutions
Solomon (1987) introduced 54 benchmark problems contained in six distinctive sets for the VRPTW, denoted by c1, c2, r1, r2, rc1, and rc2, each with 100 customer nodes. Each set highlights several factors that can affect the behavior of routing and scheduling heuristics. These factors include the geographical dispersion; the number of customers serviced by a vehicle, i.e. the relation between customer demand and vehicle capacity; and time window characteristics such as percentage of time-constrained customers, as well as the tightness and positioning of time windows. The geographical data for the first group of problem sets are randomly generated using a uniform distribution (denote the corresponding problem sets by r1 and r2). The second group of sets are clustered (denote the corresponding problems sets by c1 and c2). A third semi-clustered group of sets have a combination of randomly distributed and clustered points (denote the corresponding problem sets by rc1 and rc2. Problem sets r1, c1, and rc1 have short scheduling horizons and along with vehicular capacities only allow a few customers to be serviced by a single vehicle. Problem sets r2, c2, and rc2 have long scheduling horizons, and when combined with large vehicular capacities, allows for a much higher number of customers being serviced by a single vehicle.
Homberger and Gehring (1999) extend the original problems to include problem sets having 200, 400, 600, and 1000 customer nodes. For illustrative purposes, Figure 4.11 shows the header of one of the Homberger and Gehring (1999) problem sets, as well as the first few customers. The depot is represented by customer ‘0’. The attributes for each customer include a customer number, coordinates, the demand, the earliest and latest allowed arrival, as well as the service time at each customer. The problem sets do unfortunately not accom-modate a heterogeneous fleet, and the fleet structure proposed by Liu and Shen (1999b) is therefor used in this thesis — presented in Table 4.4 for each of the problem classes.
Time windows provided in the problem sets are hard, i.e. they allow neither early nor late arrivals. To create problem sets that will test the initial solution algorithm with soft time windows, a maximum lateness of Lmax = 30 time units is associated with each node, including the depot. Such time windows incur waiting time if arriving early, but allow late arrivals penalized at a unit cost of .
Multiple scheduling is achieved through an elementary routine testing whether their is at least time units between the return time of the current route and the end of the depot’s time window. In this thesis the author uses an arbitrary value of = 60 minutes. Tables 4.5a through 4.5f show the results for 60 problem instances executed on an Intelr Pentiumr4 computer with a 3.6GHz processor (64Bit) and 3.25GB RAM. Each table indicates the specific Homberger and Gehring (1999) problem instance from which the 100 customer data set as taken, the numbers of tours (vehicles) used in the initial solution, the total number of routes, the average time required to generate the initial solution, and the number of orphans. Orphans are customers from the data set that could not feasibly be included in the initial solution. Ten iterations were used to calculate the average time values. Orphans are a result of the specific problem instance. The time dependent travel times that were calculated using randomly generated edge types, vcT , may result in a situation whereby a customer can not be serviced within the time window of the depot, even if such customers are serviced by a dedicated vehicle.
A sample of an initial solution output file for the r2 2 3 problem set (see Table 4.5d) is provided in Appendix A. The initial solution indicates the algorithm’s ability to generate more than one route per vehicle, and indicates the vehicle type assigned to the specific route. Each line represents a route, with each route starting and ending at the depot. Sequential numbers in each route represent the customers and the sequence in which customers are serviced. In the solution for the r2 2 3 problem all nodes are routed, and no orphans exist.
1 Introduction
1.1 Modeling as research motivation
1.2 Intelligence as the research driver
1.3 Formulating the research question
1.4 Research design and methodology
1.5 The structure of the thesis
2 The Vehicle Routing Problem: origins and variants
2.1 The origins of the basic Vehicle Routing Problem (VRP)
2.2 Variants of the VRP
2.3 The integrated problem at hand
2.4 Conclusion
3 Intelligence in solution algorithms
3.1 Exact solution algorithms
3.2 A case for heuristics
3.3 Metaheuristics
3.4 Conclusion
4 An improved initial solution algorithm
4.1 A route construction heuristic
4.2 Improving the initial solution heuristic
4.3 Initial solutions
4.4 Conclusion
5 A Tabu Search solution algorithm
5.1 Elements of the tabu algorithm
5.2 Tabu algorithm
5.3 Results and analysis
5.4 Conclusion
6 A Genetic Algorithm
6.1 Initialization
6.2 Clustering
6.3 Mutation
6.4 Crossover
6.5 Evaluating crossover operators
6.6 Conclusion
7 Clustering input data
7.1 Unsupervised clustering
7.2 Evaluating fuzzy membership parameters
7.3 Validation of benchmark data
7.4 Conclusion
8 Dynamic intelligence through Artificial Neural Networks (ANNs)
8.1 Learning structures
8.2 Basic mechanisms of an Artificial Neural Network (ANN)
8.3 Representation conventions
8.4 Proposed network structure
8.5 Training the neural network
8.6 Integrating the neural network
8.7 Conclusion
9 Intelligent routing agents: birth or burial?
9.1 Answering the research questions
9.2 Critical observations and recommendations
9.3 Conclusion
Bibliography
