DOI : https://doi.org/10.18517/ijaseit.7.1.1792

Cheapest Insertion Constructive Heuristic based on Two Combination Seed Customer Criterion for the Capacitated Vehicle Routing Problem

Mansour Alssager (1), Zulaiha Ali Othman (2), Masri Ayob (3)
(1) Data mining and Optimization Group, Centre of artificial intelligence, Faculty of Information Sciences and Technology, Universiti Kebangsaan Malaysia, Selangor, Malaysia
(2) Data mining and Optimization Group, Centre of artificial intelligence, Faculty of Information Sciences and Technology, Universiti Kebangsaan Malaysia, Selangor, Malaysia
(3) Data mining and Optimization Group, Centre of artificial intelligence, Faculty of Information Sciences and Technology, Universiti Kebangsaan Malaysia, Selangor, Malaysia
Fulltext View | Download
How to cite (IJASEIT) :
Alssager, Mansour, et al. “Cheapest Insertion Constructive Heuristic Based on Two Combination Seed Customer Criterion for the Capacitated Vehicle Routing Problem”. International Journal on Advanced Science, Engineering and Information Technology, vol. 7, no. 1, Feb. 2017, pp. 207-14, doi:10.18517/ijaseit.7.1.1792.
Citation Format :
The heuristic method is a well-known constructive method for initialize trail quality solutions in capacitated vehicle routing problem. Cheapest insertion heuristic is a popular construction heuristic known for being fast, producing decent solutions, simple to implement and easy to extend handling complicated constraints. However, in previous work, there was less focus on diverse initial quality solutions. Therefore, this study proposed an extension to the cheapest insertion heuristic which consider various combinations of seed customer criteria (the first customer inserted on a route) to preserve solutions diversification. Three seed customer criteria proposed which based on the combination of two criteria based on (farthest, nearest and random criteria). The best performing criteria selected and tested on benchmark dataset, later compared with Clarke and Wright saving heuristic. The results shown that the combination of (farthest and random) criteria obtained the best initial solution which preserve balance between the quality and diversity, with less time when compared to Clarke and wright saving heuristic. This approach is for generating diverse and quality starting solutions for the capacitated vehicle routing problem.

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).