Solution approach for a large scale personnel transport system for a large company in Latin America

Garzón-Garnica, Eduardo-Arturo; Caballero-Morales, Santiago-Omar; Martínez- Flores, José-Luis Article Solution approach for a large scale personnel transport system for a large company in Latin America Journal of Industrial Engineering and Management (JIEM) Provided in Cooperation with: The School of Industrial, Aerospace and Audiovisual Engineering of Terrassa (ESEIAAT), Universitat Politècnica de Catalunya (UPC) Suggested Citation: Garzón-Garnica, Eduardo-Arturo; Caballero-Morales, Santiago-Omar; Martínez- Flores, José-Luis (2017) : Solution approach for a large scale personnel transport system for a large company in Latin America, Journal of Industrial Engineering and Management (JIEM), ISSN 2013-0953, OmniaScience, Barcelona, Vol. 10, Iss. 4, pp. 623-645, https://doi.org/10.3926/jiem.2116 This Version is available at: https://hdl.handle.net/10419/188837 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Journal of Industrial Engineering and Management JIEM, 2017 – 10(4): 623-645 – Online ISSN: 2013-0953 – Print ISSN: 2013-8423 https://doi.org/10.3926/jiem.2116 Solution Approach for a Large-Scale Personnel Transport System for a Large Company in Latin America Eduardo-Arturo Garzón-Garnica , Santiago-Omar Caballero-Morales , José-Luis Martínez-Flores Universidad Popular Autónoma del Estado de Puebla (Mexico) [email protected], [email protected], [email protected] Received: October 2016 Accepted: September 2017 Abstract: Purpose: The present paper focuses on the modelling and solution of a large-scale personnel transportation system in Mexico where many routes and vehicles are currently used to service 532 points. The routing system proposed can be applied to many cities in the Latin-American region. Design/methodology/approach: This system was modelled as a VRP model considering the use of real-world transit times, and the fact that routes start at the farthest point from the destination center. Experiments were performed on different sized sets of service points. As the size of the instances was increased, the performance of the meta-heuristic method was assessed in comparison with the results of an exact algorithm, the results remaining very close between both. When the size of the instance was full-scale and the exact algorithm took too much time to solve the problem, then the meta-heuristic algorithm provided a feasible solution. Supported by the validation with smaller scale instances, where the difference between both solutions was close to a 6%, the full–scale solution obtained with the meta-heuristic algorithm was considered to be within that same range. This solution complies with the optimal number of vehicles. Findings: The proposed modelling and solving method provided a solution that would produce significant savings in the daily operation of the routes. Originality/value: The urban distribution of the cities in Latin America is unique to other regions in the world. The general layout of the large cities in this region includes a small-town center, usually antique, and a somewhat disordered outer region. The lack of a vehicle-centered -623- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 urban planning poses distinct challenges for vehicle routing problems in the region. The use of a meta-heuristic CVRP combined with the results of an exact CVRP led to an improved routing plan specific to the requirements of the region. Keywords: capacitated vrp, tabu-search, genetic algorithms, metaheuristics 1. Introduction Logistics have become a very important part of the operation of many industries and companies. The percentage of the logistic cost in developed countries can reach 60%, and globally it can reach 30% (Kazimírová & Kazimír, 2015). In recent times, many companies, as well as public entities, pursue a reduction in the cost of their logistics operation. An improvement in the logistic network yields many advantages for the stakeholders. In large cities with industrial facilities most welfare participants commute outside of their neighborhoods to find employment (Blumenberg & Ong, 2001). This sometimes forces the employees to dedicate a large part of their daily routine to the process of traveling between their residence and their workplace. Still, there are some companies that provide this service to their employees free of charge. We will use, as an example, the case of a large scale automotive company located in the state of Puebla, Mexico. This company provides its employees with a transport service to the company’s facilities, free of charge. This service is provided through a number of buses which are assigned to a fixed number of routes. Each route has a series of pre-defined stop points, in which the person can board the bus and then to travel to the factory. Nobody is allowed to get off the bus until it arrives to its final destination. Almost all of the transport routes use a single bus, and all buses have a fixed number of seats. Public transport regulations do not allow anybody to travel standing up, so the capacity of each bus is fixed. The said company also provides additional benefits to its workforce which includes a low-cost lease of vehicles manufactured by the same company. In this way, many of the employees have a vehicle available, and this reflects in a variable demand at each point. The employees can decide some days to drive to work, instead of using the company’s transport service. However, the transport service has been working without major incidents, and the overall demand remains relatively constant. In total, the transport network consists of 47 routes which serve 728 locations (bus stops). When the served locations were analyzed, it was found that several of them were repeated. Hence, they were -624- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 consolidated into a list of 532 different locations. Each location is a point within the city or nearby cities, and is served repeatedly every day. Because this benefit represents a cost for the company, if this cost can be reduced then significant savings can be obtained for the company. These savings can contribute to extend the sets of benefits for the employees and also reduce operative costs for the company. This work is aimed to achieve these potential savings by improving the performance of the transport network. In order to achieve this objective, the transport network was modelled as a Capacitated Vehicle Routing Problem (CVRP) considering the use of real-world transit times, and the fact that routes start at the farthest location from the destination center (the company’s headquarters). Due to the size of the transport network, exact results were achieved with a commercial optimization software only for small instances of the network. In order to achieve a proposal for the complete network, a meta-heuristic algorithm was considered. This algorithm was evaluated by comparing its results with the exact results obtained with small instances. Because the mean difference between exact results and the approximate results from the meta-heuristic were smaller than 6.00%, it was assumed that the metaheuristic could provide suitable solutions for larger instances. On the complete network the meta-heuristic algorithm generated 37 routes. In contrast to the current 47 routes of the transport network, this proposal represents a saving of 47-37 = 10 routes with their associated operational costs. Hence, this work represents an important contribution to the logistic factor of the company’s transport system. The advances of this work are presented as follows: in Section 2 a literature review regarding the CVRP and insights related Latin American urban distribution within the context of vehicle routing are presented and discussed. Then, in Sections 3 and 4 the CVRP mathematical model for the exact solutions, and the meta-heuristic algorithm for the approximate solutions, are presented. The results obtained with the exact and meta-heuristic methods are analyzed in Section 5. Finally, in Section 6 our conclusions and future work are presented and discussed. -625- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 2. Literature Review Dantzig (1951) published an application of the simplex method for a transportation problem. Three years later, he performed a study on the Traveling Salesman Problem (TSP) based in the previous work (Dantzig, Fulkerson & Johnson, 1954). Later, Orloff & Caprera (1976) defined it as a vehicle routing problem. The addition of a restriction in capacity led to the naming of the problem as a Capacitated Vehicle Routing Problem, or CVRP as it was already called in the early 1990s (Li & Simchi-Levi, 1990). Kirci (2016) lists the basic components of a VRP to include vehicles, routes, depot centers, drivers, and constraints. All of these components are present in the considered transport network, and thus, the nature of the problem addressed by this study can be identified as a CVRP. One of the main problems when trying to solve a large CVRP is to obtain the data matrix. In 2015, a small portion of this specific problem was analyzed (Garzón-Garnica et al., 2015). The results of this research were not conclusive in the CVRP area because of the large amount of data that needed to be processed. The combination of the different points that needed to be served in order to obtain a distance or cost matrix proved to be extremely consuming in time and computational resources. In the case of the research by Garzón-Garnica et al. (2015), the resulting matrix contained over 50,000 different combinations. Each one of those combinations consisted of the cost of travelling from point i to point j. In this work, the cost consists of travel time. The large quantity of arcs poses a great challenge in solving these problems. In addition to that, the different possible combinations are a factor to take into account, because each combination of arcs is evaluated against the full data matrix. The search for an optimal solution transforms into billions or trillions of iterations that should be performed in order to obtain the desired optimal solution. In previous research, an optimal solution for the complete CVRP network was desired, but it was not achieved due to the amount of time required by the commercial optimization software to generate it. For smaller instances suitable solutions were achieved, however the amount of time required prevented these solutions to be usable in practical conditions (Garzón-Garnica et al., 2015). Because of this factor, a near-optimal solution will be looked upon in this work. It is expected that the obtained solution can represent a large improvement against the current state of the routes and very close to the optimal solution. The near-optimal solutions for the CVRP were obtained by means of a meta-heuristic. This was performed because the CVRP is a combinatorial problem of NP-hard complexity which cannot be solved within a reasonable polynomial time (Zhang & Lee, 2015). Although exact algorithms such as Linear -626- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 Programming (LP), Branch and Bound (BB), and Cutting Plane (CP) have been developed for the CVRP, these algorithms are either unable to solve the problem or consume too much computational cost when the size of the CVRP is large (Laporte., Gendreau, Potvin & Semet, 2000; Lin., Lee, Ying & Lee, 2009; Zhang & Lee, 2015). Research has been performed on the development of heuristics and meta-heuristics in order to provide solutions for large CVRP instances. Although classical heuristic approaches can find feasible solutions quickly, these may have a large disparity compared with best-known solutions. In such case, the meta-heuristics approaches can obtain near optimal solutions (or even global optimal solutions) for the CVRP (Lin et al., 2009). As presented by (Fink & Vob, 1999; Osman & Kelly, 1996) “meta-heuristics may be viewed as iterative processes guiding subordinate heuristics by combining intelligently different concepts of exploring and exploiting search spaces using learning strategies to structure information in order to find efficiently good or even optimal solutions”. Within the use of meta-heuristics for the CVRP, the combination of Tabu-Search (TS) with classical heuristics and/or meta-heuristics has provided feasible solutions. TS is a metaheuristic that has the following features (Campos & Mota, 2000): a) Moves: moves consist on changes between and within routes (e.g., exchanging of two clients assigned to different routes, insertion of clients, etc.). In order to avoid performing the same move and re-visiting a previously found solution (local optima) the move may be declaredas tabu (forbidden). b) Tabu List: array where the moves declared as tabu are kept.A criterion must be defined to allow the release of tabu moves. c) Admissible Move: move which is not tabu and preserves the feasibility of the solutions. d) Neighborhood: set of feasible solutions that can be obtained from a specific solution by making one move. Similarly to TS, Genetic Algorithms (GA) can provide suitable solutions for the CVRP. GA is a population-based meta-heuristic which uses evolutionary inspired operators (recombination, mutation) to generate sets of more suitable solutions (reproduction of better individuals in a population) (Wink, Bäck & Emmerich, 2012). The general features of a GA are the following: a) Initial Population: initial set of “parent” solutions (individuals). b) Fitness Evaluation: criterion to determine the suitability or “fitness” of the individual to solve a specific problem (e.g., minimum total distance, maximum savings, etc.). -627- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 c) Selection Strategy: selection technique to determine which “parent” solutions will be used to generate “offsprings” with the reproduction operators. d) Reproduction Operators: recombination (crossover) and mutation (operators based on the natural evolutionary process). e) Population Update: initial population is updated with the fittest individuals (both, from “parents” and “offsprings”). Hence, for the CVRP instance of the present work, a meta-heuristic that combined Tabu-Search (TS) and a Genetic Algorithm (GA) was used. The results obtained with this meta-heuristic corroborate the suitability of the local-search and improvement mechanisms of TS and GA. 2.1. The Particularities of Latin American Urban Distribution During three centuries, from the beginning of the 1500s to the beginning of the 1800s, most of the territories in what is currently known as Latin America, were ruled by the Spanish and Portuguese crowns (effectively becoming a colony of those reigns). The majority of the populated urban areas established during that period of time were traced under the style of the Spanish urban planning. The Interamerican Bank of Development (Banco Interamericano de Desarrollo, BID) states that the typical city in Latin America and the Caribbean is characterized by groups of informal settlements around spaces of residential or commercial neighborhoods (BID, 2011a). In a different article of the same source, it is stated that currently one third of the families in Latin America and the Caribbean face housing problems (BID, 2011b). In many cities of Latin America, there is an old town center, which usually has a main square in the form of a park, a temple, and a government building. Around this center, there can be buildings, whether public, like schools, or private, and houses and/or commerce. The usual layout of these towns or cities is rectangular and stable. The modern constructions followed that trend. However, currently the main trend is to close spaces, establishing closed communities. This closedness makes public transport difficult (Cabrerizo, 2013). The characteristics of the many cities in Latin America, and in this particular case, of the cities near the automotive plant subject of this study, pose a series of challenges when trying to obtain a solution for a CVRP. One of the main challenges is the impossibility to standardize the travelling speed of a transport vehicle. -628- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 One form of standardization would be to use direct lines between points, and then adjust the travelling speed between those points to show a travelling time close to reality. However, given the complexity of the urban settlements in Latin America, the travelling time from two different sets of points can differ greatly, considering that one set of points might be in a part of the city with large streets, and another one could be in a part with a highly dense population, and prone to traffic jams. Thus, although the distance between one set could be larger, the travelling time could be significantly smaller, and the opposite would be true for the second set of points. This alone makes it impossible to use straight lines, or Euclidean distances. To sort out this problem, a different approach was considered to obtain the distance matrix between points. And the found solution was to use a geographical information system, or GIS, that included traffic information, and used the actual routes that a vehicle could travel between points. In previous research, Garzón-Garnica et al. (2015) used the platform of Google Maps® to obtain the distance matrix for a smaller instance of this problem. It was found that it included real time information about traffic, and that the time of the day could affect the travel time. The GIS reflected these changes properly. As this method of data collection yielded the adequate travel time between each pair of points, the full data matrix was obtained using the GIS. The size of the data matrix posed its own challenge. When the full data set was obtained, the amount of different combinations accounted for 282,492. If the data matrix was to be calculated with 728 locations, the amount of different combinations would exceed half a million arcs. The VRP, and its variants, like the CVRP, have been classified as an NP-Hard problem. Different algorithms have been tested, and some exact results have been obtained. Still, the size of the instances has remained relatively small, reaching 78 or 135 points in some instances (Baldacci, Mingozzi & Roberti, 2012) In a previous research, optimal results were obtained on a small instance, using the algorithm proposed by Schrage (1999). The instance contained three routes with 27 different points. The solving algorithm was able to obtain the optimal result after 22 minutes and 30 seconds. A larger instance with 27 routes and 244 points was also processed. However, the amount of time required as well as the resources like computer memory, were not enough to obtain an optimal result (Garzón-Garnica et al, 2015). As the processing time increases with the size of the data instance, it becomes impractical to wait for the completion of the solving process. It was decided that a different method should be tried. There are two types of algorithms that can be used to solve a model: exact and heuristics algorithms. Usually heuristic algorithms use less computer time and can find an optimal or near-optimal solution in a reasonable amount of time (Gillett & Miller, 1974). -629- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 Hence, we extend on the work reported by Garzón-Garnica et al. (2015) in order to provide a complete solution for the 244-points and 532-points transport network. For this, a meta-heuristic algorithm is considered. 3. Mathematical Model for Exact Solution Being a widely-studied problem, several Capacitated Vehicle Routing Problems have been solved through different methods. When trying to find an exact solution, the algorithm used in a previous study by Garzón-Garnica et al. (2015) was used. This algorithm is the one proposed by Linus Schrage (1999) and implemented in LINGO. The same algorithm was described by different authors as Restrepo & Medina (2008). The objective function for this model is to minimize the sum of the cost associated with traveling each arc within the route, considering also that each point has to be visited once, that every vehicle must go to the final destination, and that the capacity of the vehicle must not be surpassed. The algorithm is described as follows: (1) where cij is the cost of travelling through an arc going from point i to point j and yij indicates if the arc i to j is to be travelled. Subject to: (2) which states that each location must be visited once, (3) which states that each location must be exited once, (4) which assures that there are no sub-tours, (5) -630- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 Size ObjectiveValue (OV), Routes Map 11×11 OV=1413 R1=[1-3-2-4-5-6-7-8-10-9-11-1] 20×20 OV=2197 R1=[1-3-2-4-5-6-7-8-10-9-11-12-13-1] R2=[1-15-16-17-20-18-19-14-1] 30×30 OV=3716 R1=[1-8-26-25-24-16-15-21-22-23-20-17-18-19-1] R2=[1-3-2-4-5-6-7-27-28-29-30-13-14-1] R3=[1-10-9-11-12-1] 40×40 OV=5593 R1=[1-33-34-35-36-37-38-39-40-27-28-29-30-31-1] R2=[1-3-2-4-5-6-7-8-10-9-11-12-13-32-14-1] R3=[1-26-25-24-16-15-21-22-23-20-17-18-19-1] 50×50 OV=6137 R1=[1-33-34-35-36-37-38-39-40-41-46-48-49-42- 43- 44-45-47-50-13-1] R2=[1-26-25-24-16-15-21-23-22-20-17-18-19-14-1] R3=[1-5-4-3-2-6-7-8-10-9-11-12-32-1] R4=[1-27-28-29-30-31-1] Table 2. Meta-heuristic Solutions for the CVRP with Small Instances (≤50-points) -637- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 Size Exact Meta-heuristic Error(%) 11×11 1413 1413 0.00 20×20 2197 2197 0.00 30×30 3643 3716 2.00 40×40 5438 5593 2.85 50×50 5812 6137 5.59 Table 3. Comparison of Results with Small Instances (≤50-points): Exact vs. Meta-Heuristic An issue regarding the exact methods for solving transportation problems is that optimality is based on the solution of global minimum cost. In practice, this solution may represent only a small advantage (or disadvantage) when compared with an approximate solution. As an example of this situation we present the case of the instance 40×40. The exact solution (as provided by LINGO) consists of four routes with a total time of 5438. In comparison, the meta-heuristic solution consists of three routes with a total time of 5593. While the approximate solution has an error of 2.85% it represents a “saving” of one route for the company. An attempt to solve the instance of 244 × 244 points with the exact method was realized. However, the Lingo system ran for over 900.0 hours continually until it stopped. It is unknown if the stopping was caused by a cut in the power supply of the computer, by the computer running out of memory, or by a different cause. Still, such a large processing time was deemed impractical to achieve a result. A similar situation was expected with the instance of 532 × 532 points Because, as reviewed in Table 3, the results of the meta-heuristic algorithm were consistently close to those of the exact method (considering the instances that could be solved within a reasonable amount of time), it was decided that a solution obtained by the meta-heuristic algorithm would be reliable for the case study. 5.2. Results on the Instance of 244 × 244 Points Table 4 presents the results of the meta-heuristic algorithm for the instance of 244×244 points leading to an objective value of 85052. -638- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 R1=[1-163-134-158-2-8-167-189-136-31-236-51-117-1] R2=[1-127-128-129-133-3-240-52-44-84-70-71-233-145-72- 234-1] R3=[1-210-101-81-94-106-108-201-114-68-28-29-30-10-177- 191-1] R4=[1-39-69-227-223-187-160-169-93-244-22-15-16-20-19- 205-1] R5=[1-99-198-86-27-7-9-130-147-166-159-194-17-1] R6=[1-143-109-56-212-214-215-98-97-80-199-37-115-204- 186-173-148-161-164-235-1] R7=[1-207-209-170-58-222-118-125-126 85-49-92-26-206- 32-1] R8=[1-144-87-83-123-121-239-238-11-135-181-25-23-18-1] R9=[1-197-36-45-47-50-202-122-120-73-75-21-241-151-182- 14-1] R10=[1-34-35-38-91-231-229-224-12-183-184-185-243-13- 54-1] R11=[1-33-43-46-48-230-111-6-157-152 153-155-156-178- 172-132-131-55-1] R12=[1-137-138-139-140-142-141-196-100-195-95-79-200- 102-103-213-226-232-154-146-76-1] R13=[1-41-42-89-88-112-217-64-66-67-124-176-165-190- 192-24-1] R14=[1-77-78-96-104-105-82-208-211-219-61-60-65-225-40- 203-74-119-4-149-168-1] R15=[1-57-220-110-113-237-5-171-175-162-188-179-193- 180-116-242-53-1] R16=[1-90-228-107-218-216-59-62-63-221-174-150-1] OV = 85052 Table 4. Meta-heuristic Solution for the CVRP with 244×244 points As computed by the meta-heuristic algorithm, a total of 16 routes are required to serve al 244 points. -639- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 5.3. Results on the Instance of 532 × 532 Points As previously discussed, a lower bound of 37 was defined for the number of vehicles required to serve the full transport network with 532 points. Hence, suitability of the solution generated by the meta-heuristic algorithm is assessed with this optimal number of vehicles. The results of the metaheuristic algorithm are presented in Table 5. R1=[1-380-277-252-251-278-253-282-107-102-197-42-364-70-145-159-379-1] R2=[1-323-215-287-286-289-296-83-299-225-231-74-163-192-93-205-1] R3=[1-325-324-143-88-301-476-370-69-489-174-390-12-420-369-182-1] R4=[1-459-458-170-388-172-175-397-484-482-257-300-511-179-135-410-1] R5=[1-455-456-463-91-196-359-220-64-309-496-427-450-436-504-376-1] R6=[1-457-176-186-498-124-229-230-316-20-421-422-426-473-302-1] R7=[1-322-78-82-59-254-263-268-497-508-394-127-528-181-23-235-1] R8=[1-454-165-152-431-430-11-465-31-402-365-90-441-446-1] R9=[1-211-250-132-395-4-180-451-164-518-514-522-530-75-21-1] R10=[1-469-512-291-247-383-195-48-50-120-417-272-424-243-206-1] R11=[1-33-40-444-16-114-110-87-121-238-519-521-153-462-32-1] R12=[1-470-156-157-464-133-483-493-349-292-288-38-203-30-1] R13=[1-453-212-293-222-513-354-89-416-418-439-144-337-340-46-19-1] R14=[1-129-130-515-190-346-491-485-214-216-276-85-232-126-28-1] R15=[1-56-307-306-481-532-487-310-262-506-345-161-527-529-1] R16=[1-328-333-43-227-68-112-217-413-494-128-191-531-15-419-378-1] R17=[1-382-77-198-260-125-350-385-387-393-526-520-17-409-53-1] R18=[1-516-517-7-2-167-449-432-435-236-202-261-224-440-503-1] R19=[1-381-295-414-226-84-415-122-123-509-510-178-389-524-403-1] R20=[1-140-335-142-334-100-105-281-279-207-61-267-391-149-187-13-1] R21=[1-138-331-332-361-106-96-356-248-283-213-62-63-523-184-244-1] R22=[1-467-148-348-294-266-264-366-374-47-119-353-315-117-1] R23=[1-336-357-258-492-399-162-525-183-437-442-274-55-1] R24=[1-154-472-398-57-101-249-285-360-362-298-313-71-371-372-275-1] R25=[1-44-49-314-367-22-478-204-241-406-429-168-452-273-339-1] R26=[1-97-500-35-34-41-66-411-412-486-147-155-9-150-502-1] R27=[1-80-98-99-95-94-104-246-208-58-304-255-311-308-488-177-6-92-242-1] R28=[1-319-330-139-245-79-81-111-39-115-116-438-428-26-447-185-1] R29=[1-480-103-108-290-223-265-201-423-434-401-507-3-8-189-375-1] R30=[1-137-329-326-501-86-259-312-445-479-474-475-24-52-404-14-1] R31=[1-45-51-477-239-73-400-495-303-343-188-166-136-317-1] R32=[1-460-158-471-342-490-5-351-29-443-240-408-146-76-1] R33=[1-318-363-60-65-297-67-228-233-234-270-118-392-131-448-194-1] R34=[1-141-327-320-358-199-384-210-461-171-433-425-355-407-160-54-1] R35=[1-321-200-280-218-219-284-221-505-352-27-405-72-373-18-377-1] R36=[1-468-466-151-10-386-305-256-36-338-237-271-25-169-1] R37=[1-209-109-37-341-368-113-269-347-173-396-344-134-193-499-1] Table 5. Meta-heuristic Solution for the CVRP with 532×532 points -640- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 In total, 37 routes were generated by the meta-heuristic algorithm with an O.V. of 243246. These routes comply with the optimal number of routes. In the absence of an exact solution, this result represents a suitable solution for the full transport network. This solution also represents a benchmark for future work related to this network. 6. Conclusions The challenges of logistics optimization in the Latin American region, including those pertaining to the urban trace of the city centers, as well as those of the new urbanization trends, can require the use of methods as precise as possible. About the obtention of reliable data, the characteristic urban distribution of many Latin American cities prevents the use of Euclidean distances when tryin g to solve real life Vehicle Routing Problems. In such case, the use of Geographical Information Systems represents a most reliable approach to obtain real data about travelling times and distances between network locations. Regarding the access and use of technological resources, Kim & Lee (2015) and Rodrik (2006) state that the technological growth in Latin America is slow, and in some cases failed to grow at all. Taking this into account, it is much needed to make an efficient use of the limited technological resources present in the area. Fine-tuning mathematical problems to obtain adequate results with the least amount of resources can prove to be beneficial for the logistics problems in the area in general. Obtaining an exact solution for a Large Scale Capacitated Vehicle Routing Problem proved to consume an excessive amount of computing time. This is consistent with different research documents, like the one of Baldacci et al. (2012). For the specific case of this research, the considered meta-heuristic algorithm provided consistent solutions with a mean approximation error from the exact solution of 2.08%. As the size of the instance increases it is expected that the meta-heuristic can yield results with similar approximation errors on the full-size instance. It is important to mention that meta-heuristics may or may not yield a global optimal solution, but if the global optimal is known, we may have the certainty about how close or far it is from the exact solution. In this case, a mean approximation of 2.08% is considered suitable considering the computing time of the exact method. The computing time of the exact method used for the 50 × 50 instance was too big for a practical solution to be obtained. In contrast, the meta-heuristic generated a solution with an approximation -641- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 error of 5.59% within a minute. For the 244 × 244 and 532 × 532 instances results were also obtained within a few minutes with the meta-heuristic algorithm. In contrast to the meta-heuristic, the exact method was not able to produce a solution after 900.0 hours. Hence, solutions with the meta-heuristic were obtained in a considerably lower processing time, which could also be considered as the cost of obtaining a result. Additionally, when solving routing problems, optimality is based on the solution of global minimum cost. In practice, the solution obtained by an exact method may represent only a small advantage (or disadvantage) when compared with an approximate solution. This was observed for the instance 40×40 where the exact solution consisted of four routes with a total time of 5438, and the approximate solution consisted of three routes with a total time of 5593. While the approximate solution had an error of 2.85% it represented a “saving” of one route for the company. Nevertheless, either exact or approximate methods, can lead to improved routing when compared to empirical planning. The current state of the routing service in the said company includes the use of 47 routes which serve 728 locations. The meta-heuristic solution of the routing problem determined 37 routes to serve the same locations. This represents a saving of 10 routes. Further improvements can be obtained if the requirements of each location are modelled more accurately. This is because the method used to calculate the demand, as well as the elimination of duplicate locations across routes, may affect route planning. A better calculation of the demand, attempting to obtain a more realistic number for each location, or obtaining that information directly from the company, could represent a much better solution for this model. An opportunity for future research lies in there. The number of instances that was obtained yields a difference between both methods that, if graphed, could resemble a quadratic or linear equation. Also, it may remain constant or decrease for larger instances. Because the amount of information is not enough to conclude about the convergence of the approximation error, a possible future research would be to obtain a larger number of instances, and apply statistical methods to try to obtain a better understanding of the convergence pattern between both methods. -642- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 References Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 1(218), 1-6. https://doi.org/10.1016/j.ejor.2011.07.037 BID - Banco Interamericano de Desarrollo (2011a). Un Espacio Para el Desarrollo de los Mercados de Vivienda. Ideas Para el Desarrollo en las Américas, 26(3), 26-28. BID - Banco Interamericano de Desarrollo (2011b). Una Libreta de Notas Para la Vivienda. Ideas Para el Desarrollo en las Américas, 26(3), 27-30. Blumenberg, E., & Ong, P. (2001). Cars, Buses, and Jobs: Welfare Participants and Employment Access in Los Angeles. Transportation Research Record, 1756, 22-31. https://doi.org/10.3141/1756-03 Cabrerizo, C. (2013). Ciudad y territorio en clave de paisaje urbano contemporáneo en España y México. Cuadernos de Vivienda y Urbanismo, 3(6). Campos, V., & Mota, E. (2000) Heuristic Procedures for the Capacitated Vehicle Routing Problem. Computational Optimization and Applications, 16(3), 265-277. https://doi.org/10.1023/A:1008768313174 Cordeau, J., & Laporte, G. (2005). Tabu Search Heuristics for the Vehicle Routing Problem. In Sharda, R., Stefan, V., Rego, C., & Alidaee, B. (Eds.). Metaheuristics Optimization via Memory and Evolution. Springer US. 145-163. https://doi.org/10.1007/0-387-23667-8_6 Dantzig, G.B. (1951). Application of the simplex method to a transportation problem, Activity Analysis of Production and Allocation. Cowles Commission Monograph No. 13. John Wiley & Sons, Inc., New York, N.Y.; Chapman & Hall, Ltd., London, 359-373. Dantzig, G.B., Fulkerson, D.R., & Johnson, S.M. (1954). Solution of a large scale traveling salesman problem. Technical Report P-510, RAND Corporation, Santa Monica, California. https://doi.org/10.1287/opre.2.4.393 Fink, A., & Vob, S. (1999). Generic Metaheuristics Application to Industrial Engineering Problems. Computers & Industrial Engineering, 37, 281-284. https://doi.org/10.1016/S0360-8352(99)00074-1 Garrido, P., & Castro, C. (2009). Stable solving of CVRPs using hyperheuristics. Association for Computing Machinery, 255-262. https://doi.org/10.1145/1569901.1569938 Garzón-Garnica et al. (2015). Automated Data Acquisition for a Large Scale Capacitated Vehicle Routing Problem. IFAC-PapersOnLine, 48(3), 1393-1398. https://doi.org/10.1016/j.ifacol.2015.06.281 -643- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 Gillett, B.E., & Miller, L.R. (1974). A Heuristic Algorithm for the Vehicle-Dispatch Problem. Operations Research, 22(2), 340-349. https://doi.org/10.1287/opre.22.2.340 Kazimírová, I., & Kazimír, M. (2015). Proposal of Logistic Cost Reduction in Consignment Consolidation. The International Journal of Transport & Logistics, 15(35), 1-6. Kim, Y.K., & Lee, K. (2015). Different Impacts of Scientific and Technological Knowledge on Economic Growth: Contrasting Science and Technology Policy in East Asia and Latin America. Asian Economic Policy Review, 10(1), 43-66. https://doi.org/10.1111/aepr.12081 Kirci, P. (2016). An optimization algorithm for a capacitated vehicle routing problem with time windows. Sadhana, Academy Proceedings in Engineering Sciences, 41(5), 519-529. Laporte, G., Gendreau, M., Potvin, J.Y., & Semet, F. (2000) Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7, 285-300. https://doi.org/10.1111/j.1475- 3995.2000.tb00200.x Li, C.S., & Simchi-Levi, D. (1990). Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems. ORSA Journal on Computing, 2, 64-73. https://doi.org/10.1287/ijoc.2.1.64 Lin, S.W., Lee, Z.-J., Ying, K.-C., & Lee, C.-Y. (2009) Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 36, 1505-1512. https://doi.org/10.1016/j.eswa.2007.11.060 Nazif, H., & Lee, L. (2012). Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling, 36, 2110-2117. https://doi.org/10.1016/j.apm.2011.08.010 Orloff, C., & Caprera, D. (1976). Reduction and Solution of Large Scale Vehicle Routing Problems. Transportation Science, 10(4), 361-373. https://doi.org/10.1287/trsc.10.4.361 Osman, I.H., & Kelly, J.P. (1996) Meta-Heuristics: An overview. In Osman, I.H., & Kelly, J.P. (Eds.). Meta- Heuristics: Theory & Applications. Klumer, Boston. 1-21. https://doi.org/10.1007/978-1-4613-1361-8_1 Restrepo, J.H., & Medina, P.D. (2008). A logistic case, the capacited vehicle routing problem. Scientia et Technica, 14(38), 253-258. Rodrik, D. (2006). Goodbye Washington Consensus Hello Washington confusion? A review of the World Bank’s Economic Growth in the 1990s: Learning from a Decade of Reform (2005). Journal of Economic Literature, 44 (4), 973-987. https://doi.org/10.1257/jel.44.4.973 Schrage, L. (1999). Optimization Modelling with Lingo. Chicago, Illinois, USA: Lindo Systems Inc. -644- Journal of Industrial Engineering and Management – https://doi.org/10.3926/jiem.2116 Steinhaus, M. (2015). The Application of the Self Organizing Map to the Vehicle Routing Problem. PhD Dissertation. Rhode Island, US: University of Rhode Island. Takes, F., & Kosters, W. (2010). Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem. Proceedings of the 22nd Benelux Conference on Artificial Intelligence (BNAIC 2010) . Luxembourg: University of Luxembourg - Public Research Center Henri Tudor. 1-8. Wink, S., Bäck, T., & Emmerich, M. (2012). A Meta-Genetic Algorithm for Solving the Capacitated Vehicle Routing Problem. Proceedings of the 2012 IEEE World Congress on Computational Intelligence (WCCI 2012). Brisbane, Australia, June 10-15. 1-8. https://doi.org/10.1109/CEC.2012.6253010 Zhang, D.Z., & Lee, C.K.M. (2015). An Improved Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem. Proceedings of the 2015 IEEE International Conference on Systems, Man, and Cybernetics. 2124-2128. https://doi.org/10.1109/SMC.2015.371 Journal of Industrial Engineering and Management, 2017 (www.jiem.org) Article’s contents are provided on an Attribution-Non Commercial 3.0 Creative commons license. Readers are allowed to copy, distribute and communicate article’s contents, provided the author’s and Journal of Industrial Engineering and Management’s names are included. It must not be used for commercial purposes. To see the complete license contents, please visit http://creativecommons.org/licenses/by-nc/3.0/. -645-