A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights
Vehicle routing problem lies at the heart of many service operations. The routing of service vehicles has a significant impact on the quality of the service provided. Thus, the ability to efficiently provide a delivery/collection service is crucial for company's competitiveness. This dissertati...
| Main Author: | |
|---|---|
| Format: | Dissertation (University of Nottingham only) |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/46183/ |
| _version_ | 1848797274746912768 |
|---|---|
| author | Rungkasiri, Saravit |
| author_facet | Rungkasiri, Saravit |
| author_sort | Rungkasiri, Saravit |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Vehicle routing problem lies at the heart of many service operations. The routing of service vehicles has a significant impact on the quality of the service provided. Thus, the ability to efficiently provide a delivery/collection service is crucial for company's competitiveness. This dissertation involves developing, implementing, and testing a simple heuristic for a vehicle routing problem with intermediate facilities. The vehicles have limited capacity and clients have demands. Instead of travelling back only to the main depot, the vehicles can refill their capacity at intermediate facilities, before continuing their service. The aim is to investigate the impact of introducing intermediate facilities into capacitated vehicle routing problem and identify managerial insights.
The algorithm is developed in a simple but efficient manner. The computational time is not considered in this paper. The programme can be separated into two stages. The first is giant tour construction using the well-known Clarke and Wright saving method. At this stage, vehicle capacity is temporarily ignored and a customer visiting sequence that visits all customers is generated as an output. Then, based on the sequence obtained, splitting procedure is applied to generate feasible sub-trips, with respect to vehicle capacity.
Several experiments with different routing characteristics (e.g. customer density) are tested. Each point in a graph is the average of 5 instances under similar characteristics. Results indicate that, in general, more intermediate facilities lead to more percentage improvement. When vehicle capacity is low, intermediate facilities generate greater impact. The locations also have a direct impact on the effectiveness of intermediate facilities. R2 configuration (remote depot and concentrated clients) obtains the highest percentage improvement from an introduction of intermediate facilities. However, C settings (central depot, uniformly distribute clients) benefits the most from additional intermediate facilities.
The work increases the understanding of cost saving implication for distribution managers to consider these findings before making decisions regarding intermediate facilities. With further enhancement to the algorithm, it may be extended to cope with larger instance size (e.g. 1000 customers) or even real-life application. |
| first_indexed | 2025-11-14T20:01:17Z |
| format | Dissertation (University of Nottingham only) |
| id | nottingham-46183 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:01:17Z |
| publishDate | 2017 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-461832018-04-24T14:41:13Z https://eprints.nottingham.ac.uk/46183/ A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights Rungkasiri, Saravit Vehicle routing problem lies at the heart of many service operations. The routing of service vehicles has a significant impact on the quality of the service provided. Thus, the ability to efficiently provide a delivery/collection service is crucial for company's competitiveness. This dissertation involves developing, implementing, and testing a simple heuristic for a vehicle routing problem with intermediate facilities. The vehicles have limited capacity and clients have demands. Instead of travelling back only to the main depot, the vehicles can refill their capacity at intermediate facilities, before continuing their service. The aim is to investigate the impact of introducing intermediate facilities into capacitated vehicle routing problem and identify managerial insights. The algorithm is developed in a simple but efficient manner. The computational time is not considered in this paper. The programme can be separated into two stages. The first is giant tour construction using the well-known Clarke and Wright saving method. At this stage, vehicle capacity is temporarily ignored and a customer visiting sequence that visits all customers is generated as an output. Then, based on the sequence obtained, splitting procedure is applied to generate feasible sub-trips, with respect to vehicle capacity. Several experiments with different routing characteristics (e.g. customer density) are tested. Each point in a graph is the average of 5 instances under similar characteristics. Results indicate that, in general, more intermediate facilities lead to more percentage improvement. When vehicle capacity is low, intermediate facilities generate greater impact. The locations also have a direct impact on the effectiveness of intermediate facilities. R2 configuration (remote depot and concentrated clients) obtains the highest percentage improvement from an introduction of intermediate facilities. However, C settings (central depot, uniformly distribute clients) benefits the most from additional intermediate facilities. The work increases the understanding of cost saving implication for distribution managers to consider these findings before making decisions regarding intermediate facilities. With further enhancement to the algorithm, it may be extended to cope with larger instance size (e.g. 1000 customers) or even real-life application. 2017-09-14 Dissertation (University of Nottingham only) NonPeerReviewed application/pdf en https://eprints.nottingham.ac.uk/46183/1/4282237%2C%20Saravit%20Rungkasiri%2C%20Dissertation.pdf Rungkasiri, Saravit (2017) A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights. [Dissertation (University of Nottingham only)] Clarke and Wright saving method route-first-cluster-second intermediate facilities capacitated vehicle routing |
| spellingShingle | Clarke and Wright saving method route-first-cluster-second intermediate facilities capacitated vehicle routing Rungkasiri, Saravit A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights |
| title | A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights |
| title_full | A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights |
| title_fullStr | A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights |
| title_full_unstemmed | A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights |
| title_short | A Constructive Heuristic for the Capacitated Vehicle Routing Problem with Intermediate Facilities: Experiments and Managerial Insights |
| title_sort | constructive heuristic for the capacitated vehicle routing problem with intermediate facilities: experiments and managerial insights |
| topic | Clarke and Wright saving method route-first-cluster-second intermediate facilities capacitated vehicle routing |
| url | https://eprints.nottingham.ac.uk/46183/ |