KR100470919B1 - System and method for backbone transportation planning of hub-and-spoke transportation networks - Google Patents
System and method for backbone transportation planning of hub-and-spoke transportation networks Download PDFInfo
- Publication number
- KR100470919B1 KR100470919B1 KR10-2002-0082198A KR20020082198A KR100470919B1 KR 100470919 B1 KR100470919 B1 KR 100470919B1 KR 20020082198 A KR20020082198 A KR 20020082198A KR 100470919 B1 KR100470919 B1 KR 100470919B1
- Authority
- KR
- South Korea
- Prior art keywords
- route
- transportation
- vehicle
- trunk
- hub
- Prior art date
Links
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01S—RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
- G01S19/00—Satellite radio beacon positioning systems; Determining position, velocity or attitude using signals transmitted by such systems
- G01S19/01—Satellite radio beacon positioning systems transmitting time-stamped messages, e.g. GPS [Global Positioning System], GLONASS [Global Orbiting Navigation Satellite System] or GALILEO
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/14—Digital output to display device ; Cooperation and interconnection of the display device with other functional units
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
본 발명은 허브앤스포크 물류망의 간선 운송 계획 시스템과 그 계획 생성 방법에 관한 것으로서, 특히 본 발명의 시스템은 사용자 제어 명령을 입력받는 사용자 인터페이스와, 사용자 인터페이스에 입력된 사용자 제어 명령이 임시 저장되는 임시 데이터베이스와, 사용자 제어 명령에 따라 물류망의 차량별 간선 운송 경로를 생성하되, 이의 간선 운송 경로를 평가 및 개선하는 계획 엔진과, 계획 엔진에서 생성된 운송 경로들, 운송 경로의 기준 정보, 평가 및 개선 데이터가 저장된 마스터 데이터베이스와, 임시 데이터베이스에 저장된 사용자 제어 명령에 따라 계획 엔진을 통해 차량별 간선 운송 경로를 생성하며 이의 운송 경로를 평가 및 개선하며 마스터 데이터베이스에 차량별 간선 운송 경로와, 평가 및 개선 데이터를 저장하도록 제어하는 제어 엔진을 구비한다. 따라서 본 발명은 사용자의 제어 명령을 입력받아 이를 저장하고 허브앤스포크 물류망의 간선 운송 계획시 사용자 의도에 따라 차량별 간선 운송 계획을 수행할 수 있으며 차량별 간선 운송 경로에서 경로 삽입 및 거점 교환을 통해 차량별 간선 운송 경로를 개선하며 이의 검증 절차를 통해서 최적화된 간선 운송 경로 계획을 수행할 수 있다.The present invention relates to a trunk transportation planning system of the hub and spoke logistics network and a method for generating the plan. Particularly, the system of the present invention includes a user interface for receiving a user control command and a user control command input to the user interface. A planning engine for generating vehicle-specific trunking routes in the logistics network according to a temporary database and user control commands, and a planning engine for evaluating and improving the trunking routes of the logistics network, transport routes generated by the planning engine, reference information of the transportation route, and evaluation. And the master engine, which stores the improvement data, and the user-controlled instructions stored in the temporary database, create a vehicle-specific arterial route through the planning engine, evaluate and improve its route, and the vehicle-specific arterial route in the master database. Control engine controls to store improvement data Equipped with jeans. Therefore, the present invention can receive the user's control command and store it, and can carry out the trunk transportation plan according to the user's intention when planning the trunk transportation of the hub and spoke logistics network, and the route insertion and base exchange in the trunk transportation route by vehicle It improves the trunk route of each vehicle and the optimized route route plan can be carried out through its verification process.
Description
본 발명은 물류 운송 계획 시스템 및 그 제어 방법에 관한 것으로서, 특히 사용자의 제어 명령을 토대로 간선 운송의 최적화 계획을 수행할 수 있는 허브앤스포크 물류망의 간선 운송 계획 시스템과 그 계획 생성 방법에 관한 것이다.The present invention relates to a logistics transport planning system and a control method thereof, and more particularly, to a trunk transport planning system and a plan generating method of a hub and spoke logistics network capable of performing an optimization plan for trunk transportation based on a user's control command. .
현재 물류 수송 서비스는 교통과 전자 통신 발달로 인하여 자전거 가운데 중심축인 허브와 중심축에서 뻗어 나가는 빗살들로 이루어져 있는 바퀴에 비유한 개념인 허브앤스포크 시스템(Hub-and-Spoke System)이 널리 사용되고 있다. 최근에는 공항 또는 터미널 등의 허브를 중심으로 각 지역으로 물류를 운송하는 네트워크가 구성되어 빠른 물류 운송이 이루어지고 있다.Currently, the hub-and-spoke system, which is a concept similar to a wheel composed of a hub and a comb extending from the central axis, is widely used for logistics transportation services. . Recently, a network for transporting logistics to each region centered on hubs, such as airports or terminals, has been formed, and fast logistics transportation has been achieved.
한편 지금까지 물류 운송을 계획하는 것은 차량 경로 문제를 응용한 형태이다. 차량 경로 문제는 하나 또는 그 이상의 배송 센터를 중심으로 여러 대의 차량이 센터를 출발하여 지역별로 분산된 고객들을 방문하고 다시 센터로 돌아오는 차량별 경로를 목적 함수가 최소화하도록 결정, 계획하는 것이다.Meanwhile, planning logistics transportation is an application of the vehicle route problem. The vehicle route problem is to determine and plan for the objective function to minimize the vehicle-specific route around one or more delivery centers, where multiple vehicles leave the center, visit customers distributed by region, and then return to the center.
한편 이러한 차량 경로 문제에 대한 연구는 오래 전부터 많은 결과가 문헌에 보고 되어 왔으나, 차량 경로를 생성하는데 있어 여러 가지의 제약조건이 존재하기 때문에 매우 다양한 형태의 차량 경로가 존재하게 된다. 하지만 다양한 차량 경로들을 분류하는 방법 역시 다양하다. 그 예로 차량 종류의 개수, 물류 종류의 개수, 수집과 배달의 동시 수행 여부 등에 따라 다양한 형태의 차량 경로 문제가 존재한다. 이러한 차량 경로 문제는 기본적으로 배송 센터와 고객 사이의 수요를 고려한 것이다.On the other hand, the research on the vehicle route problem has been reported in the literature for a long time, but there are various types of vehicle route because there are various constraints in creating the vehicle route. But there are also different ways to classify different vehicle routes. For example, there are various types of vehicle path problems depending on the number of vehicle types, the number of logistic types, and the simultaneous execution of collection and delivery. This vehicle route problem basically takes into account the demands between the delivery center and the customer.
도 1은 일반적인 허브앤스포크 물류망 구조를 나타낸 도면이다. 도 1을 참조하면, 간선 운송 방식이 적용된 허브앤스포크 물류망은 다음과 같다. 여러 고객들(또는 영업소)(C)의 수요를 총괄하는 하나의 허브(거점)(B)가 존재하면, 각 허브(B)들에 모아진 화물은 허브(B)들 사이의 운송을 통하여 고객에게 배달이 가능해 진다. 이때 허브(B)들 사이에 경제적 운송을 위하여 하나(혹은 여러 개)의 교환 거점(A)을 두어, 허브(B)들 사이의 화물을 교환할 수 있도록 한다. 허브들 사이의 출발지와 도착지별 운송 요구물량이 존재할 때, 허브(B)들 사이의 직접 운송 및 교환 거점(A)을 이용한 차량 별 운송이 간선운송이며, 차량 별 운송 시간 및 경로를 생성하는 것이 간선 운송 계획의 수립이다. 이러한 간선 운송 계획을 어떻게 설계하느냐에 따라 운송비가 결정됨은 물론 화물이 목적지에 도착하는 시각이 결정된다.1 is a view showing a general hub and spoke logistics network structure. Referring to Figure 1, the hub and spoke logistics network to which the trunk transportation method is applied are as follows. If there is one hub (B) that oversees the demands of several customers (or sales offices) C, the cargo collected at each hub B is delivered to the customer through the transportation between the hubs B. This becomes possible. At this time, one (or several) exchange points A are provided for economic transportation between the hubs B so that cargoes between the hubs B can be exchanged. When there is a transport requirement between origins and destinations between hubs, direct transport between hubs (B) and transport by vehicle using an exchange point (A) are inter-city transport, and creating transport time and route for each vehicle Establishment of trunk transportation plan. How you design your trunk transportation plan will determine the cost of the shipment as well as the time the cargo arrives at its destination.
이러한 간선 운송 계획은 일반적인 차량 경로 문제와는 달리, 고객들 사이에 종단 수요가 존재하는 양방향 물류흐름을 고려해야만 한다. 또한 고려해야하는 차량의 종류가 여러 가지이며 다수의 화물 종류를 취급하며, 고객들의 방문가능 시간 및 배송 센터의 시간제약이 존재하게 된다. 이러한 간선 운송 방식은 매우 복잡하고 어렵지만, 현실에 매우 근접한 모델로 물류 업체의 현실에 적용을 할 운송 계획 시스템을 개발하기 위해서는 간선 운송의 차량별 경로설정 방법이 필수적으로 요구된다. 게다가 운송 계획 시스템의 개발에 적용을 위하여 사용자의 제어 부분을 고려하여 운송 계획을 수립하고 다시 사용자의 제어가 가능하도록 하는 상황에 적용이 가능한 시스템 구조가 필요하다. This trunk transportation plan must take into account two-way logistics flows, where end-to-end demand exists between customers, unlike typical vehicle route issues. In addition, there are many different types of vehicles to consider, handling a large number of cargo types, and there is a time limit for visitor time and delivery centers for customers. Such trunk transportation method is very complicated and difficult, but in order to develop a transportation planning system that can be applied to the reality of logistics companies as a model very close to reality, a vehicle-specific routing method of trunk transportation is required. In addition, for the development of the transportation planning system, a system structure that can be applied to a situation in which a transportation plan is developed and the user can be controlled again in consideration of the user's control part is required.
본 발명의 목적은 상기와 같은 종래 기술의 문제점을 해결하기 위하여 사용자의 제어 명령을 입력받아 이를 저장하고 이에 따라 허브앤스포크 물류망의 운송 계획을 생성하는 장치를 구비함으로써 사용자 의도에 따른 차량별 간선 운송의 최적화 운송 계획을 수행할 수 있는 허브앤스포크 물류망의 간선 운송 계획 시스템을 제공하는데 있다.The object of the present invention is to receive the user's control command in order to solve the problems of the prior art as described above by having a device for storing and accordingly according to the user's intention by providing a device for generating a transport plan of the hub and spoke logistics network It is to provide trunk transportation planning system of hub & spoke logistics network that can perform transportation planning.
본 발명의 다른 목적은 사용자 제어 명령을 입력받고 이를 토대로 차량별 간선 운송 경로를 계획하고 경로 삽입 및 거점 교환을 통해 차량별 간선 운송 경로를 개선하며 이의 검증 절차를 통해서 최적화된 간선 운송 경로 계획을 수행할 수 있는 허브앤스포크 물류망의 간선 운송 계획 생성 방법을 제공하는데 있다.Another object of the present invention is to input the user control command and plan the trunk transportation route for each vehicle based on this, to improve the trunk transportation route for each vehicle by inserting the route and the base exchange and to perform the optimized trunk transportation route planning through the verification procedure It is to provide a method of generating trunk transportation plan of hub and spoke logistics network.
상기 목적을 달성하기 위하여 본 발명은 허브앤스포크 물류망의 운송 경로 계획 시스템에 있어서, 사용자 제어 명령을 입력받는 사용자 인터페이스와, 사용자 인터페이스에 입력된 사용자 제어 명령이 임시 저장되는 임시 데이터베이스와, 사용자 제어 명령에 따라 물류망의 차량별 간선 운송 경로를 생성하되, 이의 간선 운송 경로를 평가 및 개선하는 계획 엔진과, 계획 엔진에서 생성된 운송 경로들, 운송 경로의 기준 정보, 평가 및 개선 데이터가 저장된 마스터 데이터베이스와, 임시 데이터베이스에 저장된 사용자 제어 명령에 따라 계획 엔진을 통해 차량별 간선 운송 경로를 생성하며 이의 운송 경로를 평가 및 개선하며 마스터 데이터베이스에 차량별 간선 운송 경로와, 평가 및 개선 데이터를 저장하도록 제어하는 제어 엔진을 구비한다.In order to achieve the above object, the present invention provides a transportation route planning system of a hub and spoke logistics network, a user interface for receiving a user control command, a temporary database for temporarily storing a user control command input to the user interface, and user control According to the command, the main transport route for each vehicle in the logistics network is generated, and the master engine stores the planning engine for evaluating and improving the trunk transport route, the transport routes generated by the planning engine, reference information of the transport route, evaluation and improvement data. The control engine creates a vehicle-specific trunk route, evaluates and improves its route, and stores the vehicle-specific trunk route and evaluation and improvement data in the master database according to user control commands stored in the database and temporary database. A control engine is provided.
상기 다른 목적을 달성하기 위하여 본 발명은 자동화 시스템에서 허브앤스포크 물류망의 운송 경로 계획을 생성하는 방법에 있어서, 사용자 인터페이스를 통해 사용자 제어 명령을 입력받아 이를 임시 저장하는 단계와, 사용자 제어 명령에 따라 계획 엔진에서 물류망의 차량별 간선 운송 계획을 모델링하며 모델링에서 반드시 포함되는 차량 경로를 제거하는 사전처리를 통하여 초기 운송 경로를 생성하는 단계와, 모델링 및 사전 처리된 초기 운송 경로에 대해 경로 삽입 및 거점 교환을 적용하여 최소 운송 비용이 소요되는 차량별 간선 운송 경로로 개선하는 단계와, 간선 운송 경로를 확인 및 검증해서 평가한 후에 데이터베이스에 운송 경로와, 평가 및 개선 데이터를 저장하는 단계를 포함한다.In order to achieve the above object, the present invention provides a method for generating a transport route plan of a hub and spoke logistics network in an automation system, the method comprising: temporarily receiving a user control command through a user interface and temporarily storing the user control command; According to the planning engine, modeling the transportation plan for each vehicle in the logistics network and creating an initial transportation route through preprocessing that removes the vehicle route necessarily included in the modeling, and inserting a route for the modeled and preprocessed initial transportation route. And applying a node exchange to improve the trunk transportation route for each vehicle that requires the minimum transportation cost, and verifying, verifying and evaluating the trunk transportation route, and storing the transportation route and evaluation and improvement data in a database. do.
이하 첨부된 도면을 참조하여 본 발명의 바람직한 실시 예에 대해 설명하고자 한다.Hereinafter, exemplary embodiments of the present invention will be described with reference to the accompanying drawings.
도 2는 본 발명에 따른 허브앤스포크 물류망의 간선 운송 계획 시스템을 나타낸 구성도이다. 도 2를 참조하면 본 발명의 허브앤스포크 물류망의 간선 운송 계획 시스템은 사용자 인터페이스(10)와, 제어 엔진(12)과, 계획 엔진(14)과, 임시 데이터베이스(DB)(18)와, 마스터 데이터베이스(DB)(20)로 구성된다.Figure 2 is a block diagram showing the trunk transportation planning system of the hub and spoke logistics network according to the present invention. Referring to FIG. 2, the trunk transportation planning system of the hub and spoke logistics network of the present invention includes a user interface 10, a control engine 12, a planning engine 14, a temporary database (DB) 18, It consists of a master database (DB) 20.
여기서 사용자 인터페이스(10)는 사용자 제어 명령을 입력받는다. 제어 엔진(12)은 임시 데이터베이스(18)에 저장된 사용자 제어 명령에 따라 계획 엔진(14)을 통해 허브앤스포크 물류망의 차량별 간선 운송 경로를 생성하며 이의 운송 경로를 평가 및 개선하도록 제어하고, 마스터 데이터베이스(DB)(20)에 상기 간선 운송 경로와, 평가 및 개선 데이터가 저장되도록 제어한다. 계획 엔진(14)은 사용자 제어 명령에 따라 허브앤스포크 물류망의 차량별 간선 운송 경로를 생성하며 이의 운송 경로를 평가 및 개선한다.The user interface 10 receives a user control command. The control engine 12 generates a vehicle-specific trunk transportation route of the hub & spoke distribution network through the planning engine 14 according to a user control command stored in the temporary database 18, and controls to evaluate and improve the transportation route thereof. The main transport route and the evaluation and improvement data are stored in the master database (DB) 20. The planning engine 14 generates a vehicle-specific trunk transportation route of the hub & spoke logistics network according to a user control command, and evaluates and improves the transportation route thereof.
계획 엔진(14)은 모델 어뎁터(144)와, 최적화 모듈(142)과, 평가부(146)로 구성된다.The planning engine 14 is composed of a model adapter 144, an optimization module 142, and an evaluation unit 146.
여기서 계획 엔진(14)의 모델 어뎁터(144)는 사용자 제어 명령에 따라 물류망의 차량별 간선 운송 계획을 모델링하고 이의 모델링에서 반드시 포함되는 차량 경로를 제거하여 사전 처리하는 초기 운송 경로를 생성한다. 이때 사전 처리과정은 거점간 직접 경로 또는 거점과 교환거점간의 직접 경로로 운송 경로를 생성하고, 운송 비용이 적게 드는 차량 유형을 선택하고, 출발 거점에는 발생 물량을 도착 거점에는 도착 물량을 할당하여 초기 운송 경로를 생성한다.Here, the model adapter 144 of the planning engine 14 models the trunk transportation plan for each vehicle of the distribution network according to a user control command, and generates an initial transportation path by removing the vehicle path necessarily included in the modeling and preprocessing. At this time, the pre-processing process creates a transportation route by direct route between bases or direct route between base and exchange base, selects the type of vehicle which has low transportation cost, assigns the quantity to be generated at the departure point and the arrival quantity at the arrival point. Create a shipping route.
최적화 모듈(142)은 모델 어뎁터(144)에서 모델링 및 사전 처리된 초기 운송 경로에 대해 경로 삽입 및 거점 교환을 적용하여 최소 운송 비용이 소요되는 차량별 간선 운송 경로로 개선한다. 이때 각 거점별로 운송 물량을 분할한 후에 거점-교환거점-거점의 경로를 생성하고, 생성된 경로에서 하나의 경로에 대해 다른 경로가 삽입되도록 하고 경로상의 거점의 위치를 바꾸어서 경로를 변경한다.The optimization module 142 improves to the trunk-by-vehicle transportation route that requires the minimum transportation cost by applying route insertion and node exchange for the initial transportation route modeled and preprocessed in the model adapter 144. At this time, after dividing the transport volume by each node, the route of the base-exchange base-base is created, the other route is inserted into one route from the generated route, and the route is changed by changing the position of the base on the route.
그리고 계획 엔진의 평가부(146)는 최적화 모듈(142)의 운송 경로를 확인 및 검증해서 평가한다.And the evaluation unit 146 of the planning engine confirms and verifies the transportation path of the optimization module 142 and evaluates it.
임시 데이터베이스(18)는 사용자 인터페이스(10)에 입력된 사용자 제어 명령이 임시 저장된다. 마스터 데이터베이스(20)는 계획 엔진(14)에서 생성된 차량별 간선 운송 경로들, 운송 경로의 기준 정보, 평가 및 개선 데이터가 저장된다. 마스터 데이터베이스(20)의 기준 정보는 물류망의 구성 및 운송 경로에 필요한 거점 및 교환 거점 정보(위치/가용차량 수/시간 제약 등), 거점 간 거리 및 이동 시간 정보, 차량정보(유형/용량 등), 운송 화물의 종류 및 차량 별 적재 가능 정보, 또는 운송 비용 정보(거리에 따른 차량별 비용 등)이다.The temporary database 18 temporarily stores a user control command input to the user interface 10. The master database 20 stores vehicle-specific trunk transportation routes generated by the planning engine 14, reference information of the transportation route, evaluation and improvement data. The reference information of the master database 20 includes base and exchange base information (location / available number of vehicles / time constraints, etc.), distance and travel time information between bases, and vehicle information (type / capacity, etc.) required for the construction and transportation route of the logistics network. ), Type of cargo and loadable information per vehicle, or transportation cost information (cost per vehicle according to distance).
또한 본 발명의 허브앤스포크 물류망의 간선 운송 계획 시스템은 제어 엔진(12)에서 마스터 데이터베이스(20)에 저장된 기준 정보를 토대로 계획 엔진(14)의 차량별 간선 운송 경로를 그래픽 지도상에 디스플레이하는 GIS 엔진(30)을 더 포함한다.In addition, the trunk transportation planning system of the hub and spoke logistics network of the present invention displays the trunk transportation route for each vehicle of the planning engine 14 on a graphic map based on the reference information stored in the master database 20 in the control engine 12. It further comprises a GIS engine (30).
한편 본 발명의 간선 운송 계획 시스템은 DB 관리모듈(16)을 더 포함할 수 있는데, 임시 데이터베이스(DB)(18)와 마스터 데이터베이스(DB)(20)에 저장된 정보를 관리(추가, 삭제, 수정 등)한다. 이에 제어 엔진(12)은 사용자 인터페이스(12)를 통해 사용자가 데이터의 추가, 삭제, 수정 등의 데이터 관리를 요구하게 되면 DB 관리모듈(16)에 그 명령을 전달하여 임시 데이터베이스(18) 또는 마스터 데이터베이스(20)의 데이터를 추가, 삭제, 수정한다.Meanwhile, the trunk transportation planning system of the present invention may further include a DB management module 16, which manages (adds, deletes, and modifies information stored in the temporary database (DB) 18 and the master database (DB) 20). Etc.) When the user requests data management such as adding, deleting, or modifying data through the user interface 12, the control engine 12 transmits the command to the DB management module 16 to provide a temporary database 18 or a master. The data of the database 20 is added, deleted, or modified.
도 3은 본 발명에 따른 허브앤스포크 물류망의 간선 운송 계획 생성 방법을 나타낸 흐름도이다. 도 2 및 도 3을 참조하면, 본 발명에 따른 허브앤스포크 물류망에서의 간선 운송 계획 시스템은 다음과 같이 작동한다.3 is a flowchart illustrating a method for generating trunk transportation plan of a hub and spoke logistics network according to the present invention. 2 and 3, the trunk transportation planning system in the hub and spoke logistics network according to the present invention operates as follows.
우선, 제어 엔진(12)은 사용자 인터페이스(10)를 통해 허브앤스포크 물류망에서의 간선 운송 계획에 관한 사용자 제어 명령을 입력받아 이를 임시 데이터베이스(DB)(18)에 저장한다.(S10∼S12)First, the control engine 12 receives a user control command regarding trunk transportation planning in the hub and spoke logistics network through the user interface 10 and stores it in a temporary database 18 (S10 to S12). )
제어 엔진(12)은 임시 데이터베이스 DB(18)에 저장된 여러 가지 입력 정보를 읽어와서 계획 엔진(14)의 모델 어뎁터(144)를 통해 간선 운송 계획 문제를 구성한다. 여기서 임시 데이터베이스(DB)(18)로부터의 입력 정보는 거점간의 거리 및 이동시간의 정보, 차량의 정보, 화물 종류의 정보, 화물과 차량의 용량관계, 거점의 작업시간 정보 거점 별 운송 요구 화물 정보 등이다.The control engine 12 reads various input information stored in the temporary database DB 18 and constructs a trunk transportation planning problem through the model adapter 144 of the planning engine 14. In this case, the input information from the temporary database (DB) 18 includes information on distance and movement time between bases, vehicle information, cargo type information, capacity relationship between cargo and vehicle, transport time information of base, and cargo required cargo information for each base. And so on.
계획 엔진(14)의 모델 어뎁터(144)는 상기 입력된 기본 정보에 부가하여 임시 데이터베이스(DB)(18)에 저장된 사용자 제어 명령을 읽어와서 허브앤스포크 물류망의 차량별 간선 운송 경로를 수립하는데 필요한 제약을 추가하여 운송 경로 문제를 모델링한다. 그리고 최적 운송 계획을 수립하는데 요구되는 사전 처리하여 초기 차량별 간선 운송 경로를 생성한다.(S14)The model adapter 144 of the planning engine 14 reads a user control command stored in a temporary database 18 in addition to the input basic information to establish a vehicle-specific trunk transportation route of the hub & spoke logistics network. Add the necessary constraints to model the transport route problem. In addition, the preliminary processing required to establish the optimal transportation plan is generated to generate an initial vehicle-specific trunk transportation route (S14).
이때 사용자로부터 제약 또는 변화가 가능한 제어 명령은 특정 차량 경로의 임의 설정, 특정 구간의 사용 금지, 운송량의 강제 할당, 특정 운송 구간의 시간의 변경, 사용 차량의 종류 및 가용량 변경 등이 된다.At this time, the control command that can be restricted or changed by the user includes arbitrary setting of a specific vehicle route, prohibiting the use of a specific section, forcibly allocating a traffic volume, changing a time of a specific transportation section, and changing the type and capacity of the vehicle used.
그리고 사전 처리는 최적의 차량별 간선 운송 계획에 반드시 포함되는 차량 경로를 제거하여 초기 운송 경로를 생성한다.(S16) 예를 들어, 허브앤스포크 물류망의 차량별 초기 운송 경로 계획시 계획 엔진(14)은 모델 어뎁터(144)를 통해 거점간 직접 경로 또는 거점과 교환거점간의 직접 경로로 운송 경로를 생성한다. 여기서 거점간 직접경로 설정은 거점간 운송물량이 차량의 정해진 적재비율 이상인 경우 한 대의 차량으로 운송이 가능할 때까지 해당 거점간에 직접경로를 배정하여 물량을 처리하는 것을 의미하는 것으로, 돌아오는 경로는 고려하지 않으며 제약조건을 만족시키는 경우에 한해 거점 직접경로를 개설한다.The preprocessing removes the vehicle path necessarily included in the optimal trunk transportation plan for each vehicle to generate an initial transportation route. (S16) For example, a planning engine (at the time of planning the initial transportation route for each vehicle in the hub & spoke logistics network) 14 generates a transport path through a model adapter 144 as a direct path between bases or a direct path between a base and an exchange base. Here, the direct route setting between bases means that if the transport volume between the bases is more than the designated loading rate of the vehicle, the direct route is allocated between the bases and the volume is handled until it can be transported by one vehicle. If the constraints are satisfied, the direct route will be established.
모델 어뎁터(144)에서 생성된 초기 운송 경로에서는 다수의 차량 유형이 존재할 수 있으므로 차량 유형을 결정하기 위해서 차량 유형별로 운송비용을 계산한다. 그리고 가장 비용이 적게 드는 차량 유형을 선택하도록 한다. 이때 차량 유형별 운송비용은 직접 경로로 배정된 차량의 운송비용과 잔여물량의 운송비용 합으로 계산한다.Since there may be a plurality of vehicle types in the initial transportation route generated by the model adapter 144, the transportation cost is calculated for each vehicle type to determine the vehicle type. Try to choose the lowest cost vehicle type. At this time, the transportation cost of each vehicle type is calculated as the sum of the transportation cost of the vehicle allocated by the direct route and the transportation cost of the remaining quantity.
또한 모델 어뎁터(144)에서는 이와 같이 거점간 직접경로를 설정하고 난 후의 거점간 운송물량을 정한다. 차량 한 대분 미만인 물량은 모두 교환거점을 경유해 도착 거점으로 운송된다. 따라서 각 거점별로 남은 운송물량을 더해 하나의 거점에서 교환거점으로 가는 발생물량과 교환거점에서 거점으로 오는 도착물량을 계산한다. 거점의 발생물량과 도착물량이 차량의 적재비율 이상인 경우 한 대의 차량으로 운송이 가능하며, 이 경우 차량 용량제한 때문에 다른 거점을 경유하는 것이 불가능하므로 한 대의 차량으로 운송이 가능할 때까지 교환거점 직접경로를 개설하여 물량을 처리하도록 정의한다. 만약, 거점 직접경로와 교환 거점 직접경로를 설정한 후 각 거점의 발생물량과 도착물량은 각각 차량 한 대 미만이거나, 한 쪽 물량만 차량 한 대 이상인 경우가 있을 수 있다. 물량이 차량 한 대 이상인 경우 운송 계획을 수립하기 위해서는 비분할 선적 가정에 맞게 물량을 미리 분할해야 한다. 이 경우 물량을 분할하고 그 수에 맞게 거점을 생성한 후에, 하나의 거점을 출발 거점과 도착 거점으로 따로 생성해 출발 거점에는 발생물량을 할당하고 도착 거점에는 도착물량을 할당하도록 한다. In addition, the model adapter 144 determines the amount of transport between the bases after setting the direct path between the bases in this way. All less than one car is transported to the arrival point via the exchange point. Therefore, the amount of transport left by each base is added to calculate the amount of occurrence from one base to the base of exchange and the amount of arrival from the base of the exchange. If the amount of arrival and arrival of the base is more than the loading rate of the vehicle, it can be transported by one vehicle.In this case, it is impossible to pass through the other base due to the limited capacity of the vehicle. It is defined to treat quantity by opening. If the direct route and the exchange route direct route are established, the generated volume and the arrival volume of each base may be less than one vehicle, or only one volume may be more than one vehicle. If the quantity is more than one vehicle, the plan should be divided in advance to fit the unspecified shipping assumptions in order to plan transportation. In this case, after dividing the quantity and creating the bases according to the number, one base is created separately from the starting and arrival bases, so that the generation amount is assigned to the departure base and the arrival quantity is allocated to the arrival base.
이와 같이, 모델 어뎁터(144)는 출발 거점에는 발생 물량을, 도착 거점에는 도착 물량을 할당하여 최소 비용의 경로로 초기 운송 경로를 생성한다. 이에 최적화 모듈(142)은 각 거점별로 운송 물량을 분할하고자 각 거점별로 발생 물량과 도착 물량을 고려하여 물량이 차량 한 대 이상인 경우 물량을 미리 분할하는 비분할 선적을 적용한다. 비분할 선적이란 거점간 운송물량을 하나의 운송 경로를 통해서 한 대의 운송수단으로 운송하는 방안으로, 운송물량이 차량의 최대용량보다 항상 작거나 같다고 하는 가정이 내재되어 있다. 이 경우도 거점직접경로나 교환거점 경유경로의 경우와 마찬가지로 물량을 분할할 때 어떤 차량 유형을 기준으로 물량을 분할할지 결정해야 한다.In this way, the model adapter 144 assigns the amount of occurrence to the departure point and the amount of arrival to the arrival point to generate the initial transportation route with the least cost route. In this regard, the optimization module 142 applies undivided shipment that divides the quantity in advance when the quantity is one or more vehicles in consideration of the generated quantity and the arrival quantity for each base to divide the transportation quantity by each base. Non-partitioned shipment is a method of transporting the transport volume between bases in one transport through a transport route, and there is an inherent assumption that the transport volume is always less than or equal to the maximum capacity of the vehicle. In this case, as in the case of the direct route route or the exchange route, it is necessary to decide on which vehicle type to divide the volume.
그리고 최적화 모듈(142)은 각 거점별로 운송 물량을 분할한 후에 거점-교환거점-거점의 경로를 생성하고, 생성된 경로에서 하나의 경로에 대해 다른 경로가 삽입되도록 하여 경로를 변환한다.(S18) 이때 경로 변환은 변형된 삽입 휴리스틱(insertion heuristic) 방식을 적용한다. 일반적으로 삽입 휴리스틱은 경로를 하나씩 생성해 가는 방법으로 하나의 거점을 선택해 교환거점에서 거점으로, 거점에서 다시 교환거점으로 이어지는 초기 경로를 생성한 뒤 이 경로에 다른 거점을 하나씩 삽입(insert)하는 방법이다. 삽입할 거점을 선택하는 기준은 다양하며 이익을 최대로 하거나 비용의 감소를 최대로 하는 것 등을 예로 들 수 있다. 간선 운송 계획의 경우 교환거점 경유경로에서 출발 거점과 도착 거점이 같아야 하는 제한이 존재하기 때문에 각 거점을 하나씩 삽입하는 방법은 적용이 불가능하고 하나의 거점이 삽입되었을 때 비용의 감소나 이익을 계산하는 방법에도 정확한 기준이 없다. In addition, the optimization module 142 divides the transport volume for each base, generates a path of a base-exchange base-base, and converts the path by inserting another path for one path from the generated path. In this case, the path transformation applies a modified insertion heuristic scheme. In general, insert heuristics create a path one by one, and select one node to create an initial path from the exchange point to the base point and then back to the exchange point, and then insert one other point into the path. to be. The criteria for choosing a base to insert are varied, such as maximizing profit or maximizing cost reduction. In the case of trunk transportation plan, there is a restriction that the starting point and the arrival point must be the same in the route through the exchange point, so the method of inserting each point is not applicable and the cost reduction or benefit is calculated when one point is inserted. There is no exact standard in the method.
본 발명에서는 상, 하행 경로를 구분하여 가능한 삽입 방법의 비용을 계산하고, 경로의 삽입을 수행하는 변형된 삽입 휴리스틱 방식을 적용한다. 변형된 삽입 휴리스틱 방식을 통한 경로 생성하는 단계이 후, 두 경로에서 λ개 이하의 거점을 선택해 서로 교환하는 λ-경로 교환을 적용한다. 예를 들어, λ가 2인 경우 서로 다른 두 개의 경로에서 각각 한 개 또는 두 개의 거점을 선택해 서로 교환한다. 경로 교환시 상행 경로만 고려한 경우, 하행 경로만 고려한 경우, 상/하행 경로를 모두 고려한 경우의 세 가지 경우에 대해 모두 총 운송비용을 계산한다. 가능한 모든 거점 교환(interchange)을 적용해 얻어지는 해 중 가장 좋은 해를 선택하는 BI(the best-improvement) 전략을 적용한다.In the present invention, a modified insertion heuristic method of calculating the cost of a possible insertion method by dividing up and down paths and performing insertion of a path is applied. After generating the path through the modified insertion heuristic method, the λ-path exchange is applied to select and exchange λ or fewer points in the two paths. For example, if λ is 2, one or two bases are selected from two different paths and exchanged with each other. When considering only the ascending route, considering the ascending route, and considering the ascending and descending route, the total cost of transportation is calculated. Apply the best-improvement (BI) strategy to select the best solution obtained by applying all possible interchanges.
한편, 경로 삽입 및 거점 교환 과정시 최적화 모듈(142)은 차량용적 및 작업 시간대의 조건을 만족시켜야만 한다. 차량 용적 조건은 상행 경로(출발 거점에서 교환거점으로 가는 경로)와 하행경로(교환거점에서 도착 거점으로 가는 경로)에서 모든 차량은 차량의 최대용적을 초과해서는 안 된다. 작업 시간대 조건은 상행경로상의 모든 거점은 출발가능시각 이후에 출발해야 하며, 교환거점에 교환시간 이전에 도착해야 한다. 또한 교환 거점에서는 교환시간 이후에 출발해야 하며 하행경로상의 모든 거점에 도착한계시각 이전에 도착해야 한다.On the other hand, during the path insertion and base exchange process, the optimization module 142 must satisfy the conditions of the vehicle volume and the working time zone. Vehicle volume conditions shall not exceed the maximum volume of any vehicle on the uphill path (from the departure point to the exchange point) and on the downward path (from the exchange point to the arrival point). Working time zone conditions require that all points on the uphill route depart after the departure time and must arrive at the exchange point prior to the exchange time. In addition, the departure point must depart after the exchange time and arrive before the arrival time limit for all the points on the downhill route.
계획 엔진(14)은 평가부(146)를 통해 최적화 모듈(142)에서 개선된 차량별 간선 운송 경로를 확인 및 검증해서 평가한다.(S20)The planning engine 14 checks, verifies, and evaluates the vehicle-specific trunk transportation route improved by the optimization module 142 through the evaluation unit 146. (S20)
제어 엔진(12)은 평가 후, 마스터 데이터베이스(20)에 차량별 간성 운송 경로와, 평가 및 개선 데이터를 저장하고 GIS 엔진(30)을 통해 저장된 간선 운송 경로와 그 평가 및 개선 데이터를 그래픽 지도상에 디스플레이하여 사용자에게 알려준다.(S22∼S24) 여기서, 마스터 데이터베이스(20)에 저장되는 데이터는 차량의 간선 운송 경로별로 1) 차량의 유형, 총 운송 거리 및 시간, 비용 2) 출발 거점 및 경유 거점 3) 출발거점의 출발 시간 및 경유지의 도착 빛 출발시간, 4) 출발 및 경유거점의 운송 물량 등이다.After the evaluation, the control engine 12 stores the vehicle-specific simplistic transportation route and evaluation and improvement data in the master database 20 and displays the trunk transportation route and the evaluation and improvement data stored through the GIS engine 30 on a graphical map. The data stored in the master database 20 is 1) the type of vehicle, the total transport distance and time, the cost, and 2) the starting point and transit point. 3) the departure time of the departure point and the arrival light of the waypoint; and 4) the volume of transportation to and from the departure point.
이후 사용자는 디스플레이된 간선 운송 경로 그래픽 결과를 보고 다시 사용자 제약을 완화하거나 추가하여 사용자 인터페이스(10)로 새로운 간선 운송 계획의 제어 명령을 다시 입력시켜 본 발명에 따른 운송 계획을 다시 생성시킬 수 있다.The user can then view the displayed trunk transportation route graphical results again to relax or add user constraints and re-enter the control command of the new trunk transportation plan to the user interface 10 to regenerate the transportation plan according to the present invention.
이상 설명한 바와 같이, 본 발명은 사용자의 제어 명령을 입력받아 이를 저장하고 허브앤스포크 물류망의 간선 운송 계획시 사용자 의도에 따라 차량별 간선 운송 계획을 수행할 수 있다.As described above, the present invention may receive the user's control command and store it, and may carry out the trunk transportation plan for each vehicle according to the user's intention in the trunk transportation plan of the hub and spoke logistics network.
또한 본 발명은 사용자 제어 명령에 따른 차량별 간선 운송 경로에서 변형된 경로 삽입 및 거점 교환을 통해 차량별 간선 운송 경로를 개선하며 이의 검증 절차를 통해서 최적화된 간선 운송 경로 계획을 수행할 수 있다.In addition, the present invention improves the trunk transport path for each vehicle by inserting the modified route and the base exchange in the trunk transport path for each vehicle according to the user control command, and can perform the optimized trunk transport path planning through the verification procedure.
한편, 본 발명은 상술한 실시 예에 국한되는 것이 아니라 후술되는 청구범위에 기재된 본 발명의 기술적 사상과 범주 내에서 당업자에 의해 여러 가지 변형이 가능하다.On the other hand, the present invention is not limited to the above-described embodiment, various modifications are possible by those skilled in the art within the spirit and scope of the present invention described in the claims to be described later.
도 1은 일반적인 허브앤스포크 물류망 구조를 나타낸 도면,1 is a view showing a general hub and spoke logistics network structure,
도 2는 본 발명에 따른 허브앤스포크 물류망의 간선 운송 계획 시스템을 나타낸 구성도,2 is a block diagram showing the trunk transportation planning system of the hub and spoke logistics network according to the present invention,
도 3은 본 발명에 따른 허브앤스포크 물류망의 간선 운송 계획 생성 방법을 나타낸 흐름도.Figure 3 is a flow chart illustrating a method for generating trunk transportation plan of the hub and spoke logistics network in accordance with the present invention.
＜도면의 주요부분에 대한 부호의 설명＞<Description of the code | symbol about the principal part of drawing>
1 : 허브앤스포크 물류망의 간선 운송 계획 시스템1: trunk transportation planning system of hub & spoke logistics network
10 : 사용자 인터페이스 12 : 제어 엔진10: user interface 12: control engine
14 : 계획 엔진 16 : DB 관리모듈14: planning engine 16: DB management module
18 : 임시 DB 20 : 마스터 DB18: temporary DB 20: master DB
30 : GIS 엔진 40 : 지도 DB30: GIS engine 40: map DB
142 : 최적화 모듈 144 : 모델 어뎁터142: optimization module 144: model adapter
146 : 평가부 146: evaluation unit
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR10-2002-0082198A KR100470919B1 (en) | 2002-12-21 | 2002-12-21 | System and method for backbone transportation planning of hub-and-spoke transportation networks |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR10-2002-0082198A KR100470919B1 (en) | 2002-12-21 | 2002-12-21 | System and method for backbone transportation planning of hub-and-spoke transportation networks |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20040055505A KR20040055505A (en) | 2004-06-26 |
| KR100470919B1 true KR100470919B1 (en) | 2005-03-10 |
Family
ID=37348176
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR10-2002-0082198A KR100470919B1 (en) | 2002-12-21 | 2002-12-21 | System and method for backbone transportation planning of hub-and-spoke transportation networks |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR100470919B1 (en) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100685783B1 (en) * | 2005-02-18 | 2007-02-22 | 한국전자통신연구원 | System and method for setting-up the time scheduling of postal transportation network |
| KR100867373B1 (en) * | 2006-12-04 | 2008-11-06 | 한국전자통신연구원 | System and method for planning postal transportation network and recording media storing program embodying the method |
| EP2232429A4 (en) * | 2007-12-05 | 2011-10-26 | Clever Devices Ltd | Holistic multi-modal transport apparatus and method |
| KR100982622B1 (en) * | 2008-02-04 | 2010-09-15 | 홍영채 | A method for searching optimum hub locations based on a prediction about logistic cost |
| KR101040874B1 (en) * | 2008-10-20 | 2011-06-16 | 부산대학교 산학협력단 | System For Determination Of Containerships Routings In Maritime Logistics |
| CN103198533B (en) | 2013-03-21 | 2015-08-12 | 洪勇 | The defining method of mail path information and device |
| JP2021174262A (en) * | 2020-04-24 | 2021-11-01 | 富士通株式会社 | Delivery plan creation support program, delivery plan creation support method, and information processing device |
| CN114841406B (en) * | 2022-03-28 | 2024-07-12 | 深圳市跨越新科技有限公司 | Logistics trunk network planning method, device, equipment and storage medium |
-
2002
- 2002-12-21 KR KR10-2002-0082198A patent/KR100470919B1/en not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| KR20040055505A (en) | 2004-06-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Wang | Routing and scheduling for a last-mile transportation system | |
| Garaix et al. | Vehicle routing problems with alternative paths: An application to on-demand transportation | |
| Desrochers et al. | Vehicle routing with time windows: optimization and approximation | |
| Psaraftis | Dynamic vehicle routing problems | |
| Zhou et al. | An exact algorithm for the two-echelon vehicle routing problem with drones | |
| Haghani et al. | A dynamic vehicle routing problem with time-dependent travel times | |
| Prins | Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case | |
| Dullaert et al. | New heuristics for the fleet size and mix vehicle routing problem with time windows | |
| Kwon et al. | Routing and scheduling temporal and heterogeneous freight car traffic on rail networks | |
| US20080077464A1 (en) | Vehicle scheduling and routing with trailers | |
| Lee et al. | Vehicle capacity planning system: A case study on vehicle routing problem with time windows | |
| JP2000036093A (en) | Vehicle allocation device | |
| WO2001069488A1 (en) | Vehicle scheduling system | |
| Şahin et al. | A branch and price algorithm for the heterogeneous fleet multi-depot multi-trip vehicle routing problem with time windows | |
| KR100470919B1 (en) | System and method for backbone transportation planning of hub-and-spoke transportation networks | |
| JP2002302257A (en) | Delivery planning method and program for executing the same | |
| Cheung et al. | Multi-attribute label matching algorithms for vehicle routing problems with time windows and backhauls | |
| Yu et al. | Time window optimization for attended home service delivery under multiple sources of uncertainties | |
| Hao et al. | Introduction to the dynamic pickup and delivery problem benchmark--ICAPS 2021 competition | |
| Yang et al. | Winning the race to customers with micro-fulfillment centers: an approach for network planning in quick commerce | |
| JP2005043974A (en) | Method and system for forming transport schedule | |
| JP4025652B2 (en) | Transportation planning system and method | |
| Hatzenbühler et al. | Multi-purpose pickup and delivery problem for combined passenger and freight transport | |
| JPH05135070A (en) | Delivery scheduling device | |
| Campetella et al. | Freight service design for the italian railways company |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A201 | Request for examination | ||
| E902 | Notification of reason for refusal | ||
| E701 | Decision to grant or registration of patent right | ||
| GRNT | Written decision to grant | ||
| FPAY | Annual fee payment |
Payment date: 20091231 Year of fee payment: 6 |
|
| LAPS | Lapse due to unpaid annual fee |