Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
An integrated and intelligent metaheuristic for constrained vehicle routing
Thesis (PhD (Industrial Engineering))--University of Pretoria, 2007.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Published: |
University of Pretoria
2013
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613676788252672 |
|---|---|
| access_status_str | Open Access |
| author2 | Claasen, S.J. (Schalk Johannes) |
| author_browse | Claasen, S.J. (Schalk Johannes) |
| author_facet | Claasen, S.J. (Schalk Johannes) |
| collection | Thesis |
| dc_rights_str_mv | © University of Pretor |
| description | Thesis (PhD (Industrial Engineering))--University of Pretoria, 2007. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/26439 |
| institution | University of Pretoria (South Africa) |
| last_indexed | 2026-06-10T12:39:56.368Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2013 |
| publishDateRange | 2013 |
| publishDateSort | 2013 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/26439 An integrated and intelligent metaheuristic for constrained vehicle routing Claasen, S.J. (Schalk Johannes) johan.joubert@up.ac.za Joubert, Johannes Wilhelm Vehicle routing Fuzzy clustering Time-dependent travel time Metaheuristics UCTD Thesis (PhD (Industrial Engineering))--University of Pretoria, 2007. South African metropolitan areas are experiencing rapid growth and require an increase in network infrastructure. Increased congestion negatively impacts both public and freight transport costs. The concept of City Logistics is concerned with the mobility of cities, and entails the process of optimizing urban logistics activities by concerning the social, environmental, economic, financial, and energy impacts of urban freight movement. In a costcompetitive environment, freight transporters often use sophisticated vehicle routing and scheduling applications to improve fleet utilization and reduce the cost of meeting customer demands. In this thesis, the candidate builds on the observation that vehicle routing and scheduling algorithms are inherent problem specific, with no single algorithm providing a dominant solution to all problem environments. Commercial applications mostly deploy a single algorithm in a multitude of environments which would often be better serviced by various different algorithms. This thesis algorithmically implements the ability of human decision makers to choose an appropriate solution algorithm when solving scheduling problems. The intent of the routing agent is to classify the problem as representative of a traditional problem set, based on its characteristics, and then to solve the problem with the most appropriate solution algorithm known for the traditional problem set. A not-so-artificially-intelligent-vehicle-routing-agent™ is proposed and developed in this thesis. To be considered intelligent, an agent is firstly required to be able to recognize its environment. Fuzzy c-means clustering is employed to analyze the geographic dispersion of the customers (nodes) from an unknown routing problem to determine to which traditional problem set it relates best. Cluster validation is used to classify the routing problem into a traditional problem set. Once the routing environment is classified, the agent selects an appropriate metaheuristic to solve the complex variant of the Vehicle Routing Problem. Multiple soft time windows, a heterogeneous fleet, and multiple scheduling are addressed in the presence of time-dependent travel times. A new initial solution heuristic is proposed that exploits the inherent configuration of customer service times through a concept referred to as time window compatibility. A high-quality initial solution is subsequently improved by the Tabu Search metaheuristic through both an adaptive memory, and a self-selection structure. As an alternative to Tabu Search, a Genetic Algorithm is developed in this thesis. Two new crossover mechanisms are proposed that outperform a number of existing crossover mechanisms. The first proposed mechanism successfully uses the concept of time window compatibility, while the second builds on an idea used from a different sweeping-arc heuristic. A neural network is employed to assist the intelligent routing agent to choose, based on its knowledge base, between the two metaheuristic algorithms available to solve the unknown problem at hand. The routing agent then not only solves the complex variant of the problem, but adapts to the problem environment by evaluating its decisions, and updating, or reaffirming its knowledge base to ensure improved decisions are made in future. Industrial and Systems Engineering PhD unrestricted 2013-09-07T05:33:24Z 2007-08-01 2013-09-07T05:33:24Z 2007-04-20 2007-08-01 2007-07-20 Thesis Joubert, JW 2007, An integrated and intelligent metaheuristic for constrained vehicle routing, PhD Thesis, University of Pretoria, Pretoria, viewed yymmdd <http://hdl.handle.net/2263/26439> Pretoria http://hdl.handle.net/2263/26439 http://upetd.up.ac.za/thesis/available/etd-07202007-175138/ © University of Pretor application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf application/pdf University of Pretoria |
| spellingShingle | Vehicle routing Fuzzy clustering Time-dependent travel time Metaheuristics UCTD An integrated and intelligent metaheuristic for constrained vehicle routing |
| title | An integrated and intelligent metaheuristic for constrained vehicle routing |
| title_full | An integrated and intelligent metaheuristic for constrained vehicle routing |
| title_fullStr | An integrated and intelligent metaheuristic for constrained vehicle routing |
| title_full_unstemmed | An integrated and intelligent metaheuristic for constrained vehicle routing |
| title_short | An integrated and intelligent metaheuristic for constrained vehicle routing |
| title_sort | integrated and intelligent metaheuristic for constrained vehicle routing |
| topic | Vehicle routing Fuzzy clustering Time-dependent travel time Metaheuristics UCTD |
| url | http://hdl.handle.net/2263/26439 http://upetd.up.ac.za/thesis/available/etd-07202007-175138/ |