Metaheuristic Algorithms Based on Compromise Programming for the Multi-Objective Urban Shipment Problem
<p>An example of a planned path with <math display="inline"><semantics> <mrow> <mi>N</mi> <mo>=</mo> <mn>5</mn> <mo>,</mo> <mo> </mo> <msub> <mi>V</mi> <mi>k</mi> </msub> <mo>=</mo> <mn>2</mn> </mrow> </semantics></math>.</p> "> Figure 2
<p>Scanned area of the search process in the CP-based approach.</p> "> Figure 3
<p>The flow of the proposed GA scheme.</p> "> Figure 4
<p>Chromosome representation.</p> "> Figure 5
<p>Step 2 to step 5 of the crossover phase.</p> "> Figure 6
<p>Combination of GA at the <math display="inline"><semantics> <mi>g</mi> </semantics></math>th generation and local search in HGA.</p> "> Figure 7
<p>The flow of TA.</p> "> Figure 8
<p>Overview of the experimental design.</p> "> Figure 9
<p>Generated traveling paths for shippers by solving single-objective problems: (<b>A</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>1</mn> </msub> </mrow> </semantics></math>; (<b>B</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>2</mn> </msub> </mrow> </semantics></math>; (<b>C</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>3</mn> </msub> </mrow> </semantics></math>; (<b>D</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>4</mn> </msub> </mrow> </semantics></math>.</p> "> Figure 10
<p>(<b>A</b>) Change in the fitness values; (<b>B</b>) <math display="inline"><semantics> <mrow> <mo> </mo> <msub> <mi>f</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mi>O</mi> <mo>)</mo> </mrow> </mrow> </semantics></math>; (<b>C</b>) <math display="inline"><semantics> <mrow> <mo> </mo> <msub> <mi>f</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mi>O</mi> <mo>)</mo> </mrow> </mrow> </semantics></math>; (<b>D</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>3</mn> </msub> <mrow> <mo>(</mo> <mi>O</mi> <mo>)</mo> </mrow> </mrow> </semantics></math>; (<b>E</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>4</mn> </msub> <mrow> <mo>(</mo> <mi>O</mi> <mo>)</mo> </mrow> </mrow> </semantics></math> of the designed algorithms over generations/iterations.</p> "> Figure 11
<p>Number of violated constraints with corresponding iterations of the search process of HGA.</p> "> Figure 12
<p>(<b>A</b>) Fitness values; (<b>B</b>) execution time; (<b>C</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>1</mn> </msub> </mrow> </semantics></math>; (<b>D</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>2</mn> </msub> </mrow> </semantics></math>; (<b>E</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>3</mn> </msub> </mrow> </semantics></math>; (<b>F</b>) <math display="inline"><semantics> <mrow> <msub> <mi>f</mi> <mn>4</mn> </msub> </mrow> </semantics></math>; obtained with different numbers of customers to serve.</p> "> Figure 13
<p>Ten obtained solutions in 4D objective space by (<b>A</b>) GA, (<b>B</b>) TA, (<b>C</b>) HGA with different weight parameters (<b>D</b>).</p> ">
Abstract
:1. Introduction
1.1. Vehicle Routing Problem and Variants
- Capacitated Vehicle Routing Problem (C-VRP): refers to the limitation of vehicle capacity for classical VRPs. The system uses multiple vehicles and the total demand of each route does not exceed the vehicle capacity [3,4]. An extension of C-VRP is when the vehicles are heterogeneous (CH-VRP), where each vehicle may have a different capacity [5,6]. The package of products with different types can be considered as the multi product-VRP (MP-VRP) [7].
- Multi-Depot Vehicle Routing Problem (MD-VRP): For the classic VRP problem, the path of all vehicles can only start from a warehouse. In MD-VRP, the vehicles depart from multiple warehouses [7]. Torres et al. reviewed several variants of the MD-VRP, where it can combine several constraints, such as time windows, batch delivery, heterogeneous fleets, and scheduled delivery [8].
- Vehicle Routing Problem with Time Window (VRP-TW): is often encountered in many industrial applications. The time window is divided into soft time windows (delivery not within the period can be penalized) and hard time windows (delivery within the period is mandatory). VRP-TW has received much attention from researchers in recent years [9,10].
1.2. Related Works
1.3. Contributions
2. Proposed Model
- The system is set up with many delivery points corresponding to the customers.
- Packages that need to be delivered have different weights and delivery periods.
- Packages are shipped from various warehouses.
- Each package needs to be collected from the allocated warehouse.
- The delivery time between any two locations is time- and terrain-dependent. It is estimated based on statistical data from previous shipments.
- Shippers also use vehicles with different payloads and transportation costs.
- To deliver the order, the shipper may need to take several trips.
2.1. Mathematical Formulation
- represents the set of delivery points/customers.
- denotes the set of shippers.
- represents the set of warehouses.
- denotes the set of locations, where the first elements are the locations of the depots, and the last elements represent the locations of customers.
- is the vector that represents the capacity of shippers, where is the capacity of shipper th.
- is the vector that represent the freight rates of the shippers, where is the freight rate of shipper th.
- is the vector used to illustrate the weight of the orders by customers, where is the weight needed to deliver to delivery point th.
- is the vector used to illustrate the load time of the orders by customers, where is the time needed to load the package of customer th.
- is the vector that represents the appointment time of the customer, where [ respectively describes the appointment time and the time window that customer th demands for his/her order.
- , where is the distance if shipper goes from location th to location th.
- , denotes the time consumption of transportations between locations for shipper , where represents the time that shipper th takes to travel from location to location . is computed based on , which is the function to query the traveling time of shipper th from location th to location th, where represents the start time. The return value is depended on the traffic condition at time .
- is a matrix to represent the links of the warehouse that stores the orders and the delivery points. means the order of customer th is kept by warehouse th.
- is the vector that represents the number of tours each shipper takes, where is the number of tours of shipper
- The decision variable represents the planned paths for shippers, where denotes the number of tours made by the shipper th to deliver all of his/her assigned orders. Figure 1 illustrates an example of a planned path.
- represents the sequence of visited nodes of the shippers. Shipper th goes to node immediately after node in trip th if . 0 otherwise.
- where is the estimated time to deliver to the customer . If < then , and the duration is considered to be waiting time.
- where represents the total traveling time of the shipper th.
- Minimize of the transportation cost of all shippers based on types of vehicles. Traveling on long routes increases costs:
- The urban delivery requires punctuality, although this is not a hard constraint on the model. However, the less late the delivery, the more satisfied the customer. The optimizer needs to minimize late delivery to the customers:
- Serving customers is beneficial for businesses. However, it can be traded off by the convenience of the delivery staff. The workforce is usually part-time. Thus, a route that saves shippers waiting time provides a competitive environment. It is necessary to minimize the waiting time of the shippers:
- Minimize differences in traveling time of the shippers. The shipper’s working time is only counted as travel time. This does not include waiting time. Therefore, this time allocation helps to balance the workload of the shippers:
- All orders must be delivered:
- Each delivery point is assigned to only one shipper:
- The capacity of the shipper on every trip is respected:
- The shipper must load the customer’s package before delivery to the customer in the same trip:
- The shipper cannot visit more than one location at the same time:
2.2. Compromise Programming for MOP-VRP
3. Proposed Algorithms
3.1. Genetic Algorithm
- Initialize the population: The structure of the individual is equivalent to decision variable , as described in the proposed optimization model. We generate the population as the set of individuals. For programming convenience, the chromosome is represented by two arrays having the size of , denoted by and . represents the paths of the shippers by storing the identifications of customers and shippers, and arranging them in random order. Positive integers are used to represent the customer ids and negative integers are used to represent the shipper ids. is used to identify the trips of the shippers. Figure 4 shows the chromosome representation for an example of 12 customers with ids from 1 to 12, three shippers with ids 1 to 3, and two warehouses A and B. In the figure, the first three elements of are 12, 2, and 5. This means the shipper with id 1 is assigned to deliver to these customers. The corresponding elements in are binary only. A value of 0 means the shipper can directly continue to travel, whereas 1 means the shipper has to return to the related warehouse to load the package before delivering to the next customer. stores only values; in this case, it is not necessary that shipper id 1 is stored in , thus increasing the convenience of the random process.
- Fitness function: we used the compromise Euclidean distance-based function for the individual as:All proposed algorithms give optimal results for single-objective optimization problems. and can be considered as pre-computed in this procedure.
- Selection: we chose φ elite individuals and bypassed them from the crossover and mutation phase to keep them in the next generation.
- Crossover: creates a new solution that retains the good properties of its parent. We selected a crossover rate . There are five steps to implement the crossover for the remaining individuals of the next generation (see Figure 5), as follows:Step 1: Randomly select two individuals as the parents denoted byStep 2: Randomly select a substring from a parent for both and .Step 3: Create a proto-child by phasing the substring into its corresponding position.Step 4: Delete all the elements that are already in the proto-child of the remaining parents. This creates an array that contains the elements needed by the proto-child.Step 5:
- ▪
- For : Place the elements of the resulting array into the unfix position of the proto-child from left to right.
- ▪
- For : Place the elements of the resulting array into the unfix position of the proto-child in the corresponding position.
- Mutation: Modify a solution to create a new solution to expand the search space of the algorithm. We selected a mutation rate . There are two steps to implement the mutation for the remaining individuals of the next generation, as follows:Step 1: Randomly select a substring from the individual.Step 2:
- ▪
- For : shuffle the element in the substring to create a new route.
- ▪
- For : flip each element in the substring to create a new trip.
- Repair: In this phase we fix the solutions that violate the defined constraints. There are some principal rules to guide the repair process:
- ▪
- The array controls the trips of the shippers that are related to the capacity. If the customers’ weight is already surpassed for the corresponding shipper in a journey, the array must be fixed for that shipper to return for supply after the current customer.
- ▪
- We maintain the principal to minimize the number of trips; therefore, we check trips to determine if any can be removed without violating the capacity constraint, and remove these if possible.
- ▪
- At the end of each trip, the corresponding element value in the array must be 1.
- ▪
3.2. Hybrid Genetic Algorithm
3.2.1. Local Search
- Denote as the starting solution.
- Find , which is the set of neighboring solutions of .
- 3.
- Repair every solution in that violates the defined constraints.
- 4.
- Return s* = .
3.2.2. Combination of GA and Local Search
3.3. Tabu Search
4. Experimental Results
4.1. Experimental Design
4.2. Results
- is the solution in the Pareto solution set that is generated by the algorithm.
- denotes the oriented axes hypercube that is formulated by points and in the objective space.
- denotes the volume of the hypercube in the objective space.
5. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Informed Consent Statement
Data Availability Statement
Conflicts of Interest
References
- Toth, P.; Vigo, D. (Eds.) The Vehicle Routing Problem; Society for Industrial and Applied Mathematics: Philadelphia, PA, USA, 2002. [Google Scholar]
- Mor, A.; Speranza, M.G. Vehicle routing problems over time: A survey. 4OR 2020, 18, 129–149. [Google Scholar] [CrossRef]
- Kır, S.; Yazgan, H.R.; Tüncel, E. A novel heuristic algorithm for capacitated vehicle routing problem. J. Ind. Eng. Int. 2017, 13, 323–330. [Google Scholar] [CrossRef] [Green Version]
- Bouzid, M.C.; Haddadene, H.A.; Salhi, S. An integration of Lagrangian split and VNS: The case of the capacitated vehicle routing problem. Comput. Oper. Res. 2017, 78, 513–525. [Google Scholar] [CrossRef]
- Lai, D.S.; Demirag, O.C.; Leung, J.M. A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transp. Res. Part E Logist. Transp. Rev. 2016, 86, 32–52. [Google Scholar] [CrossRef]
- Yu, V.F.; Redi, A.A.N.P.; Hidayat, Y.A.; Wibowo, O.J. A simulated annealing heuristic for the hybrid vehicle routing problem. Appl. Soft Comput. 2017, 53, 119–132. [Google Scholar] [CrossRef]
- Alemany, G.; Juan, A.A.; Garcia, R.; Garcia, A.; Ortega, M. Multi-capacity, Multi-depot, Multi-product VRP with Heterogeneous Fleets and Demand Exceeding Depot Capacity. In Applied Mathematics and Computational Intelligence; FIM 2015; Advances in Intelligent Systems and Computing; Gil-Lafuente, A., Merigó, J., Dass, B., Verma, R., Eds.; Springer: Cham, Switzerland, 2018; Volume 730. [Google Scholar] [CrossRef]
- Montoya-Torres, J.R.; Franco, J.L.; Isaza, S.N.; Jimenez, H.A.F.; Herazo-Padilla, N. A literature review on the vehicle routing problem with multiple depots. Comput. Ind. Eng. 2015, 79, 115–129. [Google Scholar] [CrossRef]
- Zhen, L.; Ma, C.; Wang, K.; Xiao, L.; Zhang, W. Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transp. Res. Part E Logist. Transp. Rev. 2020, 135, 101866. [Google Scholar] [CrossRef]
- Tirkolaee, E.B.; Abbasian, P.; Soltani, M.; Ghaffarian, S.A. Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study. Waste Manag. Res. J. Sustain. Circ. Econ. 2019, 37, 4–13. [Google Scholar] [CrossRef] [Green Version]
- Cattaruzza, D.; Absi, N.; Feillet, D. Vehicle routing problems with multiple trips. 4OR 2016, 14, 223–259. [Google Scholar] [CrossRef]
- Li, W.; Wu, Y.; Kumar, P.N.R.; Li, K. Multi-trip vehicle routing problem with order release time. Eng. Optim. 2020, 52, 1279–1294. [Google Scholar] [CrossRef]
- Han, M.; Wang, Y. A Survey for Vehicle Routing Problems and Its Derivatives. IOP Conf. Ser. Mater. Sci. Eng. 2018, 452, 042024. [Google Scholar] [CrossRef]
- Pan, B.; Zhang, Z.; Lim, A. Multi-trip time-dependent vehicle routing problem with time windows. Eur. J. Oper. Res. 2021, 291, 218–231. [Google Scholar] [CrossRef]
- Ma, Y.; Han, J.; Kang, K.; Yan, F. An Improved ACO for the Multi-depot Vehicle Routing Problem with Time Windows. In Proceedings of the Tenth International Conference on Management Science and Engineering Management; Advances in Intelligent Systems and Computing; Xu, J., Hajiyev, A., Nickel, S., Gen, M., Eds.; Springer: Singapore, 2017; Volume 502. [Google Scholar] [CrossRef]
- Zhang, W.; Gajpal, Y.; Appadoo, S.S.; Wei, Q. Multi-Depot Green Vehicle Routing Problem to Minimize Carbon Emissions. Sustainability 2020, 12, 3500. [Google Scholar] [CrossRef] [Green Version]
- Nucamendi-Guillén, S.; Padilla, A.G.; Olivares-Benitez, E.; Moreno-Vega, J.M. The multi-depot open location routing problem with a heterogeneous fixed fleet. Expert Syst. Appl. 2021, 165, 113846. [Google Scholar] [CrossRef]
- Shelbourne, B.C.; Battarra, M.; Potts, C.N. The Vehicle Routing Problem with Release and Due Dates. INFORMS J. Comput. 2017, 29, 705–723. [Google Scholar] [CrossRef]
- Ojstersek, R.; Brezocnik, M.; Buchmeister, B. Multi-objective optimization of production scheduling with evolutionary computation: A review. Int. J. Ind. Eng. Comput. 2020, 11, 359–376. [Google Scholar] [CrossRef]
- Dutta, J.; Barma, P.S.; Mukherjee, A.; Kar, S.; De, T.; Pamučar, D.; Šukevičius, Šarūnas; Garbinčius, G. Multi-objective green mixed vehicle routing problem under rough environment. Transport 2021, 1–13. [Google Scholar] [CrossRef]
- Bahri, O.; Ben Amor, N.; Talbi, E.-G. Robust Routes for the Fuzzy Multi-objective Vehicle Routing Problem. IFAC-PapersOnLine 2016, 49, 769–774. [Google Scholar] [CrossRef]
- Gunantara, N. A review of multi-objective optimization: Methods and its applications. Cogent Eng. 2018, 5, 1502242. [Google Scholar] [CrossRef]
- Okabe, T.; Jin, Y.; Sendhoff, B. A critical survey of performance indices for multi-objective optimisation. In Proceedings of the 2003 Congress on Evolutionary Computation, Chicago, IL, USA, 12–16 July 2003. CEC ’03. [Google Scholar] [CrossRef] [Green Version]
- Lysgaard, J.; Wøhlk, S. A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 2014, 236, 800–810. [Google Scholar] [CrossRef]
- Elhallaoui, I.; Villeneuve, D.; Soumis, F.; Desaulniers, G. Dynamic Aggregation of Set-Partitioning Constraints in Column Generation. Oper. Res. 2005, 53, 632–645. [Google Scholar] [CrossRef] [Green Version]
- Guimarans, D.; Herrero, R.; Riera, D.; Juan, A.A.; Ramos, J.J. Combining probabilistic algorithms, Constraint Programming and Lagrangian Relaxation to solve the Vehicle Routing Problem. Ann. Math. Artif. Intell. 2011, 62, 299–315. [Google Scholar] [CrossRef]
- Coello, C.A.C.; Van Veldhuizen, D.A.; Lamont, G.B. Evolutionary Algorithms for Solving Multi-Objective Problems; Springer: Boston, MA, USA, 2002. [Google Scholar]
- Liu, Z.; Zhou, K.; Jiang, F.; Zhen, Y. Application of MTabu in VRPTW. In Proceedings of the 2017 International Conference on Computer Systems, Electronics and Control (ICCSEC), Dalian, China, 25–27 December 2017; pp. 392–395. [Google Scholar] [CrossRef]
- Kurnia, H.; Wahyuni, E.G.; Pembrani, E.C.; Gardini, S.T.; Aditya, S.K. Vehicle Routing Problem Using Genetic Algorithm with Multi Compartment on Vegetable Distribution. IOP Conf. Ser. Mater. Sci. Eng. 2018, 325, 012012. [Google Scholar] [CrossRef]
- Cortes, I.R.; Aguilar, J.A.H.; Ruiz, M.Á.; Cruz-Chavez, M.A.; Arroyo-Figueroa, G. Design and Implementation of a CVRP Simulator Using Genetic Algorithms. Res. Comput. Sci. 2018, 147, 35–47. [Google Scholar] [CrossRef]
- Fitriana, R.; Moengin, P.; Kusumaningrum, U. Improvement Route for Distribution Solutions MDVRP (Multi Depot Vehicle Routing Problem) using Genetic Algorithm. IOP Conf. Ser. Mater. Sci. Eng. 2019, 528, 012042. [Google Scholar] [CrossRef]
- Rabbouch, B.; Saâdaoui, F.; Mraihi, R. Efficient implementation of the genetic algorithm to solve rich vehicle routing problems. Oper. Res. 2021, 21, 1763–1791. [Google Scholar] [CrossRef]
- Euchi, J.; Sadok, A. Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones. Phys. Commun. 2021, 44, 101236. [Google Scholar] [CrossRef]
- Mahrach, M.; Miranda, G.; León, C.; Segredo, E. Comparison between Single and Multi-Objective Evolutionary Algorithms to Solve the Knapsack Problem and the Travelling Salesman Problem. Mathematics 2020, 8, 2018. [Google Scholar] [CrossRef]
- Mnasri, S.; Nasri, N.; Bossche, A.V.D.; Val, T. 3D indoor redeployment in IoT collection networks: A real prototyping using a hybrid PI-NSGA-III-VF. In Proceedings of the 2018 14th International Wireless Communications & Mobile Computing Conference (IWCMC), Limassol, Cyprus, 25–29 June 2018; pp. 780–785. [Google Scholar]
- Mnasri, S.; Nasri, N.; AlRashidi, M.; Bossche, A.V.D.; Val, T. IoT networks 3D deployment using hybrid many-objective optimization algorithms. J. Heuristics 2020, 26, 663–709. [Google Scholar] [CrossRef]
- Chugh, T.; Sindhya, K.; Hakanen, J.; Miettinen, K. A survey on handling computationally expensive multiobjective optimization problems with evolutionary algorithms. Soft Comput. 2019, 23, 3137–3166. [Google Scholar] [CrossRef] [Green Version]
- Ngo, S.T.; Jaafar, J.; Aziz, I.A.; Nguyen, G.H. Introduction to A Compromise Programming Based Method for Complex Scheduling and Planning Problems. In Proceedings of the 2021 4th International Conference on Information Management & Management Science (IMMS’21), Chengdu, China, 27–29 August 2021; ACM: New York, NY, USA, 2021; pp. 133–138. [Google Scholar] [CrossRef]
- Ringuest, J.L. Compromise Programming. In Multiobjective Optimization: Behavioral and Computational Considerations; Springer: Boston, MA, USA, 1992. [Google Scholar]
- Ngo, S.T.; Jafreezal, J.; Nguyen, G.H.; Bui, A.N. A Genetic Algorithm for Multi-Objective Optimization in Complex Course Timetabling. In Proceedings of the 2021 10th International Conference on Software and Computer Applications, Kuala Lumpur, Malaysia, 23–26 February 2021; pp. 229–237. [Google Scholar]
- Ngo, S.T.; Jaafar, J.B.; Aziz, I.A.; Nguyen, G.H.; Bui, A.N. Genetic Algorithm for Solving Multi-Objective Optimization in Examination Timetabling Problem. Int. J. Emerg. Technol. Learn. (iJET) 2021, 16, 4–24. [Google Scholar] [CrossRef]
- Son, N.; Jaafar, J.; Aziz, I.; Anh, B. A Compromise Programming for Multi-Objective Task Assignment Problem. Computers 2021, 10, 15. [Google Scholar] [CrossRef]
- Ngo, T.S.; Bui, N.A.; Tran, T.T.; Le, P.C.; Bui, D.C.; Nguyen, T.D.; Phan, L.D.; Kieu, Q.T.; Nguyen, B.S.; Tran, S.N. Some Algorithms to Solve a Bi-Objectives Problem for Team Selection. Appl. Sci. 2020, 10, 2700. [Google Scholar] [CrossRef] [Green Version]
- Son, N.T.; Jaafar, J.; Aziz, I.A.; Anh, B.N. Meta-Heuristic Algorithms for Learning Path Recommender at MOOC. IEEE Access 2021, 9, 59093–59107. [Google Scholar] [CrossRef]
- Son, N.T.; Jaafar, J.; Aziz, I.A.; Anh, B.N.; Binh, H.D.; Aftab, M.U. A Compromise Programming to Task Assignment Problem in Software Development Project. Comput. Mater. Contin. 2021, 69, 3429–3444. [Google Scholar] [CrossRef]
- Ngo, S.T.; Jaafar, J.; Van Doan, T.; Lac, D.P.; Bui, A.N. The Effectiveness of Reference Point Selection Methods for Compromise Programming in Multi-Criteria Learning Path Search Algorithm. In Proceedings of the 2021 4th International Conference on Information Management & Management Science (IMMS’21), Chengdu, China, 27–29 August 2021; ACM: New York, NY, USA, 2021; pp. 133–138. [Google Scholar] [CrossRef]
- Katoch, S.; Chauhan, S.S.; Kumar, V. A review on genetic algorithm: Past, present, and future. Multimed. Tools Appl. 2021, 80, 8091–8126. [Google Scholar] [CrossRef] [PubMed]
- De Oca, M.A.M.; Cotta, C.; Neri, F. Local Search. In Handbook of Memetic Algorithms; Studies in Computational Intelligence; Neri, F., Cotta, C., Moscato, P., Eds.; Springer: Berlin/Heidelberg, Germany, 2012; Volume 379. [Google Scholar] [CrossRef]
- Gendreau, M.; Potvin, J.-Y. Tabu Search. In Search Methodologies; Burke, E.K., Kendall, G., Eds.; Springer: Boston, MA, USA, 2005. [Google Scholar] [CrossRef]
- Ishibuchi, H.; Imada, R.; Masuyama, N.; Nojima, Y. Comparison of Hypervolume, IGD and IGD+ from the Viewpoint of Optimal Distributions of Solutions. In Evolutionary Multi-Criterion Optimization; EMO 2019; Lecture Notes in Computer Science; Springer: Cham, Switzerland, 2019; Volume 11411. [Google Scholar] [CrossRef]
- Emmerich, M.T.M.; Deutz, A.H. A tutorial on multiobjective optimization: Fundamentals and evolutionary methods. Nat. Comput. 2018, 17, 585–609. [Google Scholar] [CrossRef] [Green Version]
Research | Objective Functions | VRP Types | Highlights | Drawbacks |
---|---|---|---|---|
Zhen et al., 2020 [9] | Minimize traveling time of all the vehicles. | MD-VRP, MT-VRP, VRP-TW | The proposed mixed integer linear programming can clearly describe the business. The proposed metaheuristics can provide optimal solutions on a large scale. | The model is not based on a realistic problem where the data is also randomly selected from the benchmark. The model does not involve several factors such as traffic conditions. |
Babaee Tirkolaee et al., 2019 [10] | Minimize the sum of vehicle cost, traveling cost, penalty cost of soft time window. | MT-VRP, VRP-TW | A case study is investigated to evaluate the applicability of the proposed model in the real world. Many business conditions have been considered. | The business rules assume that the time and cost of a route is the same for all vehicles. This may not be guaranteed in other real-life applications. The designed solver can solve the problem in small and medium sizes that only offers near-optimal solutions compared to the CPLEX solver. |
Alemany et al., 2018 [7] | Minimizing distribution cost and distance-based cost. | C-VRP, MP-VRP, MD-VRP | The model was developed from a realistic case study from an oil provider company. | Experiments are conducted on a small-scale dataset. Evaluations of the proposed method did not show its performance with different techniques. |
Pan et al., 2021 [14] | Minimizing the traveling cost. | MT-VRP, VRP-TW | The routing solver was designed for a vending cafe company to replenish stocks for their geographically dispersed outlets. The proposed method can work on large-scale instances. | Authors simulate the experimented data by randomly creating data based on an existing dataset. |
Ma et al., 2017 [15] | Minimizing traveling cost. | MD-VRP, VRP-TW | An improved ACO algorithm with some ideal to improve the search speed was introduced to solve the proposed problem. | The system considers only a single depot, which is not guaranteed in several applications. The research did not show the evaluations of the proposed algorithm using the existing methods. |
Zhang et al., 2020 [16] | Minimize carbon emission. | MD-VRP | The research develops a new extension model of MD-VRP. The proposed algorithms can deal with large-scale datasets. | The proposed mathematical model and the heuristic algorithm provide better quality than the heuristic but with more computational cost. |
Nucamendi-Guillén et al., 2021 [17] | Minimize the cost of transport and contracts. | CH-VRP, MD-VRP | The proposed model was obtained from a real-world business. | Business rules are simple. The designed metaheuristic was only tested with a small-scale dataset. |
Li et al., 2020 [12] | Minimize completion time of vehicles. | MT-VRP, VRP-TW | The solver can be applied to some real-life problem instances. The proposed heuristic algorithm shows a better result than that of the CPLEX solver. | The model is simple and cannot be adapted to other businesses. The designer did not consider the concerns of different stakeholders in the system. |
Shelbourne et al., 2017 [18] | Minimize the sum of total distance cost and total weighted tardiness. | VRP-TW | Proposed solvers based on heuristics were used to evaluate the performance on several datasets. | The optimization model was based on several assumptions that may not be applied to other situations |
Item | Info |
---|---|
CPU | Intel(R) Core (TM) i5-8350U CPU @ 1.70 GHz 1.90 GHz |
RAM | Corsair Vengeance LPX 8 GB |
Programming Platform | Java 8 |
Operating System | Windows 10 |
Parameter | GA | HGA | TA |
---|---|---|---|
Population size | 1000 | 100 | 1 |
Crossover rate | 0.9 | 0.9 | None |
Mutation rate | 0.3 | 0.3 | None |
Selection rate | 0.1 | 0.1 | None |
Stop condition | 100 | 100 | 100 |
Neighborhood structure | None | Replace | Replace |
Scanned Neighbors | None | 1000 | - |
Tabu tenure | None | None | 3 |
1 | 699.32 | 5045.18 |
2 | 0 | 701,979.5 |
3 | 0 | 12,137.6 |
4 | 1.35 | 9582.21 |
Algorithm | Solution Quality | Average Time (min) | ||||||
---|---|---|---|---|---|---|---|---|
Average Fitness | Best Solution | Worst Fitness | ||||||
Fitness | ||||||||
TA | 0.052 | 0.048 | 0.076 | 0.079 | 0.021 | 0.027 | 0.055 | 25.4 |
GA | 0.073 | 0.068 | 0.041 | 0.096 | 0.013 | 0.057 | 0.076 | 5.35 |
HGA | 0.050 | 0.045 | 0.047 | 0.068 | 0.016 | 0.034 | 0.053 | 12.6 |
1 | 3-28-4-3-2-1-102-124-148-154-110-146-123-132-94-137-115-204-205-203-114-158 | 107.9532 | 8350.7 | 4.4 | 0.255 |
2 | 1-2-4-3-5-60-184-188-198-51-52-162-141-75-40-93-143-92-128-160-67-199-200-29-108-18-66-96-113-171-25-138-44-35-71-179-2-3-152-32 | 125.272 | 5687.2 | 57.3 | 141.555 |
3 | 5-4-2-202-126-151-147-107-142-156-190-193-127-100-30-145-112-165 | 96.75424 | 6272.4 | 1.9 | −6.895 |
4 | 5-4-1-3-43-173-125-78-22-6-56-176-81-169-76 | 78.75142 | 973.15 | 0 | −37.845 |
5 | 5-2-3-4-1-170-13-79-55-20-185-19-129-15-195-197-24-182-109-136-164-150-133-65-27-201-33-180-99-80-50 | 110.138 | 4980.6 | 0 | −0.395 |
6 | 3-9-4-1-175-7-38-59 | 24.40988 | 149 | 0 | −118.295 |
7 | 2-4-3-1-5-117-57-134-103-11-14-192-42-41-161-186-166-62-72-23-177-16-194-31-183-10-46-74-58-68 | 101.6263 | 7904.1 | 0 | 0.055 |
8 | 5-1-4-3-2-36-187-105-89-39-90-88-116-206-106-159-86-172-168-155-163-12-97 | 89.68427 | 3929.95 | 28.3 | −0.845 |
9 | 5-4-3-2-1-178-101-149-181-130-84-82-48-8-191-49-157-189-21-34-77-120-153-91-174-53-131-63-69-37-85-118 | 87.14513 | 4240.15 | 92.3 | 22.205 |
10 | 5-1-2-4-3-87-47-83-73-111-26-119-70-121-64-17-122-167-61-140-104-98-45-54-139-144-196 | 84.42806 | 5860.5 | 14.4 | 0.205 |
Algorithm | |
---|---|
TA | 0.938 |
GA | 0.885 |
HGA | 0.941 |
Parameter/Criteria | Applied/Obtained by NGSA-2 | Applied/Obtained by CP-Based GA |
---|---|---|
Population | 10,000 | 1000 |
Stop Condition | 1000 | 100 |
Crossover rate | 0.8 | 0.9 |
Mutation rate | 0.3 | 0.3 |
Average Execution Time (min) | ~372 | ~5 |
Number of Solutions | ~8837 | 1 |
1422 | 699.32 | |
0 | 0 | |
0 | 0 | |
42 | 1.35 | |
Best fitness value | 0.122 | 0.0689 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Ngo, T.S.; Jaafar, J.; Aziz, I.A.; Aftab, M.U.; Nguyen, H.G.; Bui, N.A. Metaheuristic Algorithms Based on Compromise Programming for the Multi-Objective Urban Shipment Problem. Entropy 2022, 24, 388. https://doi.org/10.3390/e24030388
Ngo TS, Jaafar J, Aziz IA, Aftab MU, Nguyen HG, Bui NA. Metaheuristic Algorithms Based on Compromise Programming for the Multi-Objective Urban Shipment Problem. Entropy. 2022; 24(3):388. https://doi.org/10.3390/e24030388
Chicago/Turabian StyleNgo, Tung Son, Jafreezal Jaafar, Izzatdin Abdul Aziz, Muhammad Umar Aftab, Hoang Giang Nguyen, and Ngoc Anh Bui. 2022. "Metaheuristic Algorithms Based on Compromise Programming for the Multi-Objective Urban Shipment Problem" Entropy 24, no. 3: 388. https://doi.org/10.3390/e24030388