자원 재배치를 위한 차량 경로계획의 다목적 최적화
Multi-objective Optimization of Vehicle Routing with Resource Repositioning
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
This paper deals with a vehicle routing problem with resource repositioning (VRPRR) which is a variation of well-known vehicle routing problem with pickup and delivery (VRPPD). VRPRR in which static repositioning of public bikes is a representative case, can be defined as a multi-objective optimization problem aiming at minimizing both transportation cost and the amount of unmet demand. To obtain Pareto sets for the problem, famous multi-objective optimization algorithms such as Strength Pareto Evolutionary Algorithm 2 (SPEA2) can be applied. In addition, a linear combination of two objective functions with weights can be exploited to generate Pareto sets. By varying weight values in the combined single objective function, a set of solutions is created. Experiments accomplished with a standard benchmark problem sets show that Variable Neighborhood Search (VNS) applied to solve a number of single objective function outperforms SPEA2. All generated solutions from SPEA2 are completely dominated by a set of VNS solutions. It seems that local optimization technique inherent in VNS makes it possible to generate near optimal solutions for the single objective function. Also, it shows that trade-off between the number of solutions in Pareto set and the computation time should be considered to obtain good solutions effectively in case of linearly combined single objective function.
Abstract
This paper deals with a vehicle routing problem with resource repositioning (VRPRR) which is a variation of well-known vehicle routing problem with pickup and delivery (VRPPD). VRPRR in which static repositioning of public bikes is a representative case, can be defined as a multi-objective optimization problem aiming at minimizing both transportation cost and the amount of unmet demand. To obtain Pareto sets for the problem, famous multi-objective optimization algorithms such as Strength Pareto Evolutionary Algorithm 2 (SPEA2) can be applied. In addition, a linear combination of two objective functions with weights can be exploited to generate Pareto sets. By varying weight values in the combined single objective function, a set of solutions is created. Experiments accomplished with a standard benchmark problem sets show that Variable Neighborhood Search (VNS) applied to solve a number of single objective function outperforms SPEA2. All generated solutions from SPEA2 are completely dominated by a set of VNS solutions. It seems that local optimization technique inherent in VNS makes it possible to generate near optimal solutions for the single objective function. Also, it shows that trade-off between the number of solutions in Pareto set and the computation time should be considered to obtain good solutions effectively in case of linearly combined single objective function.
참고문헌 (17)
- Braysy, O., "Vehicle Routing Problem with Time Windows, Part I : Route Construction and Local Search Algorithms", Transportation Science, 39(1), pp.104~118 (2005)
- Caggiani, L., "A Dynamic Simulation Based Model for Optimal Fleet Repositioning in Bike-Sharing Systems", Procedia-Social and Behavioral Sciences, 87, pp.203~210 (2013)
- Chemla, D., "Bike Sharing Systems : Solving the Static Rebalancing Problem", Discrete Optimization, 10, pp.120~146 (2013)
- Deb, K., "A Fast and Elitist Multiobjective Genetic Algorithm : NSGA-Ⅱ", IEEE Transactions on Evolutionary Computation, 6(2), pp.182~197 (2002)
- Gaspero, L. D., "Constraint-Based Approaches for Balancing Bike Sharing Systems", LNCS, 8124, pp.758~773 (2013)
- Hernandez-Perez, H., "A Branchand-Cut Algorithm for a Traveling Salesman Problem with Pickup and Delivery", Discrete Applied Mathematics, 145, pp.126~139 (2004)
- Hansen, P., "Variable Neighborhood Search : Methods and Applications", Annals of Operations Research, 175(1), pp.367~407 (2010)
- Konak, A., "Multi-objective Optimization using Genetic Algorithms : A Tutorial", Reliability Engineering and System Safety, 91, pp.992~1007 (2006)
- Nebro, A.J, "SMPSO : A New PSO-based Metaheuristic for Multi-Objective Optimization", IEEE Symposium on Computational Intelligence in Multi-Criteria Decision Making, pp.66~73 (2009)
- Rainer-Harbach, M., "A PILOT", VND, LNCS, pp.2013, 8111[DOI]
- Rainer-Harbach, M., "Balancing Bicycle Sharing Systems : A Variable Neighborhood Search Approach", LNCS, 7832, pp.121~132 (2013)
- Raviv, T., "Optimal Inventory Management of a Bike-Sharing Station", IIE Transactions, 45(10), pp.1077~1093 (2013)
- Raviv, T., "Static Repositioning in a Bike-Sharing System : Models and Solution Approaches", EURO Journal on Transportation and Logistics, 2(3), pp.187~229 (2013)
- Schuijbroek, J., "Inventory Rebalancing and Vehicle Routing in Bike Sharing Systems", European Journal of Operations Research, 257(3), pp.992~1004 (2013)
- Uchoa, E., "New Benchmark Instances for the Capacitated Vehicle Routing Problem", European Journal of Operations Research, 257(3), pp.845~858 (2017)
- 임동순, "공공 자전거 정적 재배치에의 VNS 알고리즘 적용", 한국경영과학회지, 41(1), pp.41~53 (2016), 한국경영과학회[DOI]
- Zitzler, E., "Multi-objective Evolutionary Algorithms : A Comparative Case Study and the Strength Pareto Approach", IEEE Trans. Evol. Comput., 3, pp.257~271 (1999)