다품종 구분배송을 위한 다용량 차량경로문제
Heterogeneous Fleet Vehicle Routing Problem with Heterogeneous Products
1
조회
0
다운로드
9
인용
0
참고문헌
키워드
초록
기존의 일반적 VRP 모형은 수요지에서의 수요를 무게 혹은 개수로 일괄 인식하여 품종별 수요가 상이한 경우에 있어 구분배송계획을 수립하는데 제한이 된다. 인터넷 전자상거래 활성화 및 개인 택배물량 증가 등으로 점점 복잡해지는 현실의 물류 환경을 고려한다면 그러한 제한사항은 물류 환경을 정밀하게 묘사하는데 걸림돌이 된다. 본 연구는 이러한 제한사항을 해결할 수 있는 수요지별 다품종 구분배송을 위한 HVRPHP(HVRP with heterogeneous products) 모형을 제안한다. 기존의 VRP 관련연구가 소품목 대량운송에 초점을 맞추었다면 본 연구는 다품목 소량운송에 적합한 모형에 대한 연구라 할 수 있다. 또한 본 연구는 다품목 소량운송을 위한 모형을 기반으로 하되 이를 변형하여 가장 늦게 배송을 완료하는 차량의 이동시간을 최소화하는 모형을 제안한다. 이는 가장 늦게 물품을 수취하는 소비자의 대기시간을 최소화하여 시간지연에 따른 불만으로 인한 이탈고객을 예방하는 효과를 제공한다. 다품목 소량 운송을 위한 HVRPHP 모형과 이를 변형한 고객 이탈을 예방하는 최장시간 대기 소비자의 대기시간 최소화 모형은 점점 복잡해지는 물류환경에서 택배회사의 배송계획 수립시 효율적 의사결정을 지원하는 모형이라 판단된다.
Abstract
The heterogeneous fleet vehicle routing problem(HVRP) is a variant of the classical vehicle routing problem in which demand points are served by a heterogeneous fleet of vehicles with various capacities, fixed costs and variable costs. However all the past study of VRP(or HVRP) does not consider product division at the demand point. Therefore it's impossible to set up detailed delivery plan how many(or much) quantities of several products should be loaded in a vehicle for satisfaction of demand points. We propose a new conceptual HVRPHP(HVRP with heterogeneous products) model considering heterogeneous products based on HVRP. We construct instance with 15 demand points, 15 kinds of products, and 2 heterogeneous vehicles. Optimal solution of this experiment is got by CPLEX. We also suggest minimizing longest waiting time model based on this HVRPHP. This model is to minimize the longest waiting time consumer's waiting time.
참고문헌 (21)
- 서상범, "국가물류비 산정 및 추이 분석" (2007), 한국교통연구원
- 조한선, "전국 교통혼잡비용 산출과 추이 분석" (2008), 한국교통연구원
- Berger,J., "A hybrid genetic algorithm for the vehicle routing problem with time windows", Article in press, Computers & Operations Research, 31(12), pp.2037~2053 (2004)
- Choi,E., "A column generation approach to the heterogeneous fleet vehicle routing problem", Computer & Operations Research, 34, pp.2080~2095 (2007)
- Clark,G., "Scheduling of vehicle from a central depot to a number of delivery points", Operations Research, 12, pp.568~581 (1964)
- Dantzig,G.B., "The Truck Dispatching Problem", Management Science, 6(1), pp.80~91 (1959)
- Dueck,G., "New optimization heuristics:the great deluge algorithm and the record-to-record travel", Journal of Computational Physics, 104, pp.86~92 (1993)
- Fagerholt,K, "Optimal fleet design in a ship routing problem", International Transactions In Operational Research, 6(5), pp.453~464 (1999)
- Gendreau,M., "A tabu search heuristic for the heterogeneous fleet vehicle routing problem", Computer and Operations Research, 26, pp.1153~1173 (1999)
- Glover,F., "Tabu search and adaptive memory problem programming : advances, applications and challenges", pp.1~76 (1997), Interfaces in comp. Sc. and Oper. Res
- Golden,B., "The fleet size and mix vehicle routing problem", Computer & Operations Research, 11, pp.49~66 (1984)
- Homberger,J., "A two-phase hybrid metaheuristic for the vehicle routing problem with time windows", European Journal of Operational Research, 162, pp.220~238 (2004)
- Imran,A., "A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem", European Journal of Operational Research, 197(2), pp.509~518 (2008)
- Li,F., "A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem", Computers and Operations Research, 34, pp.2918~2930 (2007)
- Miller C.E., "Integer programming formulation of traveling salesman problems", Journal of Association for Computing Machinery, 7, pp.326~329 (1960)
- Mosheiov,G, "Vehicle Routing with Pick-up and Delivery:Tour-Partitioning Heuristics", Computers and Industrial Engineering, 34(3), pp.669~684 (1998)
- Ochi,L.S., "A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet", Future Generation Computation System(FGCS), 14, pp.285~292 (1998)
- Salhi,S., "Incorporating vehicle routing into the vehicle fleet composition problem", European Journal of Operation Research, 66, pp.313~330 (1993)
- Taillard,E., "A parallel tabu search heuristic for the vehicle routing problem with time windows", Transportation Research Part C:Emerging Technologies, 5(2), pp.109~122 (1997)
- Taillard,E.D., "A heuristic column generation method for heterogeneous fleet", Recherche operationnelle(RAIRO), 33, pp.1~14 (1999)
- Wu,T., "Heuristic solutions to multi-depot location problem", Computers & Operations Research, 29, pp.1393~1415 (2002)