The flexible routing with flex for the fast delivery

TaeJoon Park(박태준),Yerim Chung(정예림) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.9

본 논문의 목적은 빠른 배송을 위한 배송 차량의 유연 회차와 크라우드쉬핑(Crowd Shipping) 배달원인 플렉스를 활용한 “유연 회차와 플렉스” 방식을 제안하고, 풀이 알고리즘을 제안하는 것이다. 알고리즘은 선행 연구에서 성능이 검증된 2-opt를 사용하여 차량 경로를 계산하고, 절약 휴리스틱(Saving heuristic)을 변형한 방식으로 플렉스에 할당할 고객을 계산한다. 알고리즘은 차량과 플렉스를 분리하는 것이 아니라, 상호 보완적으로 운용될 수 있게 한다. 이를 위해 차량 정보가 플렉스 할당 과정에 고려되도록 하였다. 본 연구의 실험은 다양한 도심지의 상황을 상정한 Random, Mixed, Cluster 인스턴스로 구성되었다. 실험 결과 모든 인스턴스에서는 플렉스의 사용이 차량 유연 회차의 효율성을 높여주는 것을 확인하였다. 또 플렉스와 배송 지연 시간 비용에 대한 민감도분석에서는 “유연 회차와 플렉스”가 차량만을 사용하는 방식의 차량 대수에 따라 값에 차이를 보였지만, 플렉스 비용이나 배송 지연 시간 비용이 200% 증가하는 경우에도 우위를 유지하는 것을 확인하였다. 본 연구의 결과는 플렉스가 차량과 연계되어 활용되는 경우, 플렉스에 의해 서비스되는 고객뿐만 아니라 차량으로 서비스되는 고객들의 서비스 품질을 높일 수 있음을 보여준다. In this paper, we propose “flexible routing with flex” to provide fast delivery by using the flexible routing for the delivery vehicle and crowd-shipper named flex. To this end, we have introduced an algorithm that can build the delivery plan for delivery vehicles and flexes. The introduced algorithm uses the 2-opt algorithm to construct routes with low complexity and acceptable quality, and the revised saving algorithm to assign customer orders to the flex. The algorithm allows the vehicle and the flex to function complement each other without separating the delivery vehicle from the flex. The experiments consider the 3 different instances named Random, Mixed, Cluster, and show that “the flexible routing with flex” has a better result than “vehicle only”. The sensitivity analysis of the flex cost and time penalty shows “the flexible routing with flex” can provide better service not only to the customers who are serviced by flex but also to the customers who are serviced by the delivery vehicle.

Autonomous Delivery Robot Operating System for 24-hour Delivery Service

Seu-jan Kim,Tai-Won Um 한국디지털콘텐츠학회 2023 The Journal of Contents Computing Vol.5 No.2

The demand for last-mile delivery is increasing due to the rise of ecommerce and urbanization trends, leading to various social problems. To address these problems, the introduction of autonomous delivery robots is being researched. However, most studies on delivery robots for the last mile sector assume customer attendance delivery, so it is essential to develop robots capable of door-to-door delivery. This paper proposes a 24-hour delivery operation system for urban environments. The system uses door-to-door delivery robots and applies a combinatorial optimization strategy based on deep reinforcement learning using algorithms such as STRUCT2VEC, LSTM and ATTENTION. This enables the system to solve routing problems effectively and in a short time to meet customer requirements.

재고전략 및 네트워크 구성에 따른 배송차량의 운영특성 연구

원민수,강경우 대한교통학회 2010 대한교통학회지 Vol.28 No.5

Recently, interest in supply chain management is rising along with the increasing oil prices and traffic congestion. In particular, people started studying the issue, but realized that advantageous strategies for suppliers and retailers are not always advantageous to a carrier. Therefore, in this study the atuhors set up a simulation scenario to understand delivery vehicle routing problems under various inventory policies, namely Economic Order Quantity (EOQ) and Periodic Order Quantity (POQ) and network configurations. First, the authors made a virtual supply chain. Then they analyzed characteristics of delivery vehicle routing under various inventory policies (EOQ and POQ) and network configurations. As a result, the POQ inventory policy decreases the number of vehicles, the number of drivers, and the service time of vehicles. Also, the centralized network increases the load factor of vehicles and decreases the service time of vehicles. In other words, the centralized network and the POQ inventory policy are better for the carrier. These results show a savings of 15,556,806 won ($13,389.10) in a month: a reduction of 17%. 최근 유류비와 도로혼잡의 증가, 환경오염에 대한 높은 관심으로 인하여 공급체인에서 수송부분에 대한 다양한 이슈가 제시되고 있다. 특히, 공급자와 소매상에 유리한 전략들이 운송회사 입장에서도 반드시 유리하지 않다는 이슈가 제시되면서 다양한 연구가 시도되기 시작하였다. 그러므로 본 연구에서는 전통적인 공급체인분석 관점에서 벗어나 운송회사 입장에서 재고전략 및 네트워크 구성에 따른 공급체인의 운영특성을 파악하고, 그에 따른 운송회사의 운영환경을 해석하고자 한다. 분석방법은 가상의 공급체인을 구성하고, 각 네트워크(분산형, 집중형)구성에서 EOQ재고전략(Economic Order Quantity)과 POQ재고전략(Periodic Order Quantity)에 따른 배송차량의 운영특성(배송차량의 적재율, 소요대수, 운행시간 등)을 TranCAD프로그램을 이용하여 분석하였다. 분석결과, 재고전략이 EOQ 재고전략에서 POQ 재고전략으로 바뀌면 운송회사가 보유해야 하는 배송차량과 운전자의 수를 줄일 수 있었으며, 차량 운행시간이 감소하였다. 또한 네트워크 구성이 분산형에서 집중형으로 변경되면 차량 적재율이 향상되고 차량 운행시간이 감소하였다. 즉, 운송회사 입장에서는 분산형 네트워크에서 EOQ 재고전략을 이용하는 것보다는 집중형 네트워크를 구성하고 POQ 재고전략을 이용하는 것이 유리하다는 사실을 확인 할 수 있었으며, 이러한 효과는 월 1,300만원의 고정비와 월 260만원의 변동비 절감효과를 가져왔다.

택배차량의 표준운송원가 산정시 핵심성공 요인에 관한 연구

홍상태 ( Sang Tai Hong ) 한국로지스틱스학회 2020 로지스틱스연구 Vol.28 No.3

Among the domestic transportation industry, the implementation of the fare and fare reporting system is institutionalized in the Passenger Transport Business Act (Article 9) as a bus and taxi industry. On the other hand, general freight transportation has been converted into a rate autonomy system, and the confusion of the freight transportation market is increasing due to the lack of standards for freight transportation rates due to intensifying competition among transportation companies. Recently, the government announced a policy to introduce the standard transportation cost system to stabilize the freight transportation industry. However, there is a difference in delivery fee depending on the operation type of the freight vehicle, the size of the operator, and the type of the vehicle. Therefore, it is necessary to calculate the standard transportation cost by categorizing them into business type, vehicle size, and vehicle type. In this study, the composition and calculation of production cost for standard transportation cost calculation were set for the parcel delivery · staging vehicles among general freight transportation businesses. Since labor costs account for a large portion of the standard cost calculation items, the standard cost of transportation was calculated by setting scenarios for each standard of labor cost application. As the handling fee of the freight service industry becomes an autonomous competition system, the freight service consumers are confused because the delivery fees among the freight companies are different. In the freight industry, the competition for lowering fee is being intensified and the quality of freight service is declining low management. Therefore, it is necessary to stabilize the freight service industry through the calculation of the standard transportation cost of freight vehicles.

P-중앙값과 보로노이 다이어그램을 활용한 복합적 주행환경에서의 무인 배송로봇 협력배송경로 구현을 위한 이동가능지점 선정 방안 연구

김경현(Kyunghyun Kim),김성우(Seong-Woo Kim) 적정기술학회 2022 적정기술학회지(Journal of Appropriate Technology) Vol.8 No.2

최근 자율주행 기술이 크게 발달하면서 노동집약적이고 위험한 환경에서의 배송업무의 로봇 적용이 시도되고 있다. 드론과 모바일 배송 로봇 등과 같이 다양한 크기와 목적으로 구현된 무인 배송 로봇이 개발되었지만, 제한된 주행 특성으로 배송지까지의 물류배송을 구현하기 위해서는 여러 배송 로봇의 협력이 필요로 하다. 이 연구에서는 다양한 주행환경을 극복하기 위한 여러 배송 로봇의 협력주행 시나리오를 구축하였다. 1대의 자율주행 화물 차량과 5대의 모바일배송 로봇으로 차도와 인도를 주행하는 주행영역을 비교분석을 하여, 이동가능지점 선정에 활용하였다. 화물 차량은 차도와 인도에서 주행 가능한 5대의 모바일 배송 로봇을 이동가능지점에 하차시켜, 모바일 배송 로봇이 차량접근이 불가능한 배송지로 물품을 이송할 수 있도록 한다. 모바일 배송 로봇이 배송지까지 최소이동 거리를 가지는 이동가능지점을 찾기 위해, 본 논문에서는 P-중앙값과 보로노이 다이어그램 꼭짓점을 사용하여 선정하였으며, 각 방법론의 특징과 결과를 비교 분석하여 보로노이 다이어그램 방법론의 위치선정문제 적용 가능성을 확인하였다. P-중앙값을 사용한 이동가능지점은 실제 도로의 거리를 토대로 계산되었으며, 짧은 평균 이동 거리를 가진다. 보로노이 다이어그램 방법론은 위치정보를 토대로 유클리디언 거리를 이용하기에, 이동가능지점을 선정하는데 계산시간이 P-중앙값에 대비하여 짧다. 그 결과 물류배송 중 발생하는 상황에서 보로노이 다이어그램 방법론의 사용 적용성이 있다고 판단되며, 도로정보와 인프라가 부족한 험지와 오지에서도 활용 가능성이 있다고 보인다. With the recent development of autonomous driving technology, various unmanned vehicles such as serving robots, mobile delivery robots, and drones have been developed. However, each robot has a different driving area, so it is necessary to find cooperative route for optimal unmanned delivery. In this paper, a cooperative scenario of an autonomous courier vehicle and five mobile delivery vehicles perform unmanned delivery tasks. The courier vehicle moves from a warehouse to the second hierarchy point, and drops off the five mobile delivery vehicles in order to transport goods to the doorstep of the destinations. We define the second hierarchy point by using the P-Median method and the Voronoi diagram method, and compare the results of each method using real map data. The points using P-Median are calculated based on the actual road distance and have shorter average moving distance than the Voronoi diagram method. The Voronoi diagram uses the Euclidian distance based on location information, which defines the second hierarchy point faster than the P-Median method. By comparing the results, we consider the Voronoi diagram method have capability in the cooperative multi-vehicle delivery route problem. The result of this paper have potential to be used in rough and remote areas where road information and infrastructure are lacking.

아파트 단지내 택배차량 탄소배출 분석모형에 관한 연구

배솔 ( Sol Bae ),김경석 ( Gyeongseok Kim ) 한국로지스틱스학회 2018 로지스틱스연구 Vol.26 No.2

택배차량은 택배를 배송지에 전달하기 위한 목적이 있는 통행으로 일반차량과 달리 잦은 정차와 재시동, 공회전이 많은 특성을 가지고 있다. 그러나 이전의 연구들은 택배차량의 이동 특성을 고려하지 않고 기존의 이산화탄소 발생량을 산정 방식으로 산정하여 이산화탄소 발생량이 적게 산정되는 문제점이 발생하게 되었다. 본 연구에서는 택배차량의 움직임을 이동과 시동, 공회전으로 세분하여 이에 대한 각각의 탄소배출 분석모형 제시하여 이산화탄소 택배차량의 특성이 반영된 이산화탄소 산정모델을 개발하는 것에 목적을 두고 있다. 또한 본 연구에서 제시한 산정모델을 이용하여 산정된 이산화탄소 발생량과 기존 산정모델을 이용하여 산정된 이산화탄소 발생량을 비교하였다. 일반모형을 사용하여 산정된 이산화탄소 발생량과 본 연구에서 제시한 모형을 사용하여 산정된 이산화탄소 발생량을 비교한 결과 본 연구에서 제시한 모형으로 산정된 이산화탄소 발생량이 최대 31.93%, 최소 15.55% 증가하였으며, 평균 21.44%가 증가하는 것으로 분석되었다. A parcel delivery vehicle differs from other general cars because of its purpose of delivery service that has unique characteristics, such as extremely frequent stopping, restarting and idling. However, a majority of previous studies were conducted without considering the characteristics of the parcel delivery vehicle in the calculation of carbon dioxide emission. This erroneously leads to the low amount of carbon dioxide emission in the result. Therefore, this study will consider the parcel delivery vehicle characteristics, such as stopping, starting and idling in the analysis of each type of carbon emission model. Also, the purpose of this study is to develop a carbon dioxide estimation model that reflects the characteristics of the delivery vehicle. Besides the purpose of this study is to develop a carbon dioxide estimation model that can reflects the characteristics of the parcel delivery vehicle, as well as to compare carbon dioxide emission model obtained from this study with the existing model. From the model comparison the proposed model predicts an increase by 31.93% at the maximum, 15.55% at the minimum, and 21.4% at the average.

유전알고리즘을 활용한 차량-드론 중복방문 분할배송문제 연구

박경호 ( Gyeongho Park ),김수환 ( Suhwan Kim ) 한국로지스틱스학회 2021 로지스틱스연구 Vol.29 No.2

ROK military is promoting the introduction of various types of unmanned combat systems for future warfare. Prior to the fully unmanned combat phase, it is expected that unmanned systems will assist the current human combatants. ROK military is also making efforts to introduce various types of military drones and Unmanned Ground Vehicles. The problem of delivering goods using vehicle and drones has already been studied in various ways, but since single and one-time delivery is common, it is difficult to directly apply to the military logistic situations in battlefield. The purpose of this study is to find out the fastest route and assignment of nodes to vehicle(UGV) and drones which has completely different capacities and velocities in the battlefield environment. In this study, it is allowed that demands of each node could devided and also UGV and drones could visit each nodes multiple times if they need. This study suggests a mathematical formula model to solve this problem. It also suggests a method of genetic algorithm and develop a chromosome representation composed of three strings to solve this model in polynomial time. Numerical experiments were performed on various cases by comparing the proposed mathematical model with a genetic algorithm, and the results were compared to verify the mathematical model and the efficiency of the proposed algorithm.

Aircraft delivery vehicle with fuzzy time window for improving search algorithm

C.C. Hung,T. Nguyen,C.Y. Hsieh Techno-Press 2023 Advances in aircraft and spacecraft science Vol.10 No.5

Drones are increasingly used in logistics delivery due to their low cost, high-speed and straight-line flight. Considering the small cargo capacity, limited endurance and other factors, this paper optimized the pickup and delivery vehicle routing problem with time windows in the mode of "truck+drone". A mixed integer programming model with the objective of minimizing transportation cost was proposed and an improved adaptive large neighborhood search algorithm is designed to solve the problem. In this algorithm, the performance of the algorithm is improved by designing various efficient destroy operators and repair operators based on the characteristics of the model and introducing a simulated annealing strategy to avoid falling into local optimum solutions. The effectiveness of the model and the algorithm is verified through the numerical experiments, and the impact of the "truck+drone" on the route cost is analyzed, the result of this study provides a decision basis for the route planning of "truck+drone" mode delivery.

Ground Vehicle and Drone Collaborative Delivery Planning using Genetic Algorithm

송교원,문정호 항공우주시스템공학회 2020 항공우주시스템공학회지 Vol.14 No.6

Global e-commerce and delivery companies are actively pursuing last-mile delivery service using drones, and various delivery schedule planning studies have been conducted. In this study, separate individual route networks were constructed to reflect drone route constraints such as prohibited airspace and truck route constraints such as rivers, which previous studies did not incorporate. The A* algorithm was used to calculate the shortest path distance matrix between the starting point and destinations. In addition, we proposed an optimal delivery schedule plan using genetic algorithms and applied it to compare the efficiency with that of vehicle-only delivery.

배송기사 노동부하 감소를 위한 저상형 택배 차량의 개선안 사용성 평가

이석,이순교,박지현,황규선 한국로지스틱스학회 2022 로지스틱스연구 Vol.30 No.6

In recent days, parcel delivery volume has increased by about 28% in 21 years compared to 2019 years before the outbreak of COVID-19 due to the expansion of the non-face-face consumption market and the continuous expansions of the e-commerce transaction market. In addition, as the market that requires overnight delivery increases, the situation that requires fast and large quantities of delivery. However, the areas where courier logistics trucks are not allowed to enter are gradually expanding, due to the height problem of the courier trucks. The problem of the work load of delivery drivers has been raised due to the accessibility problem in areas where the infrastructure is weak, and it is expanding to a social problem. Therefore, this study proposes two low-floor courier vehicle using EV(Electronic Vehicle) to reduce the workload of the labors according to the battery location. The proposed vehicle is designed with a low-floor types while increasing storage space compared to conventional trucks. As a result, it is expected that loading and unloading labor load will be decreased by solving the accessibility problem. In addition, to evaluate the usability of the proposed vehicles, a survey was conducted with 255 courier labors to derive expected effects and improvements. Through this study, it is expected that the productivity of the courier are able to increased and the workload of courier labor can be reduced.