V2V(Vehicle to Vehicle) 집화 및 배송체계의 간선차량 순환노선 설정문제

정동진,이기주,채준재 한국물류과학기술학회 2023 물류과학기술연구 Vol.4 No.1

The speed and efficiency of pickup and delivery of e-commerce products have become important in customers’ choice. Recently, a vehicle to vehicle (V2V) pickup and delivery system was suggested by a company that guarantees same-day delivery at a lower rate than the conventional courier service or point to point (P2P) delivery service. The V2V system may operate on relatively small infrastructural investments as the products are transferred from vehicle to vehicle that are continuously circulating trunk line routes. This study proposes a way of creating the circulating routes by formalizing the cyclic trunk line routing problem (CTLRP). A mixed integer programming approach is provided, and the model is solved using CPLEX. Then, the study provides examples of implementation on some major cities in South Korea. The analysis on the case studies shows that the V2V system can significantly reduce the delivery distance (time) required per an item compared to the P2P system.

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.

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.

Max–Min Fairness Approach for Collaborative Vehicle Routing Cost Allocation

Shunichi Ohmori,Kazuho Yoshimoto 대한산업공학회 2021 Industrial Engineeering & Management Systems Vol.20 No.3

We consider a collaborative vehicle-routing problem involving two or more companies jointly operating delivery fulfillment. It is known that the collaborative routing improves the delivery efficiency that results in a lower cost, CO₂ emission, and traffic congestions. However, cost allocation is a major challenge in the establishment of collaboration because each company has a set of customers whose locations and demands are different. In this paper, we propose an optimization-based framework for determining the optimal vehicle routing and cost allocation of companies in a collaboration, in an unbiased manner. The proposed method relies on max–min fairness that is a widely accepted concept. We formulated this problem as a multi-objective optimization problem. Thereafter, we reformulated the single-objective problem in which the fairness is considered by maximizing the minimum utility of each company in the collaboration. We quantify the utility by applying a fuzzy membership function based on the gained cost benefit. We present computational results ranging from 10 to 80 customers. In all cases, significant improvements are observed in the cost-benefit balance each company gains over the one obtained through the methods compared.

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만원의 변동비 절감효과를 가져왔다.

상호대차 요청 도서 운송량 최대화를 위한 차량 이동 방법 연구

임희종,이상복,박성재 한국문헌정보학회 2017 한국문헌정보학회지 Vol.51 No.2

There are many systematic approaches to manage Interlibrary loan (ILL) efficiently. In this paper, we propose an operating method reducing user-waiting in ILL. Users are usually informed to wait around two to three days in a regional ILL service. The reason of the waiting is that there is inefficiency in running material-delivery vehicles. A mixed integer programming is employed to resolve this issue. It provides an optimal vehicle-route maximizing material-deliveries subject to time availability. We used an actual data of a regional ILL system to provide optimal vehicle routes under different time settings. 상호대차 서비스 운영의 효율화를 위해서 시스템적 접근과 같은 다양한 방법이 모색되고 있다. 본 연구는 그 가운데 상호대차 대출 요청의 이용자 대기시간을 줄일 수 있는 운영관리 방법에 대해서 제시하였다. 지역 내 상호대차 대출의 이용자 대기 시간은 2~3일로 안내되고 있는데 이와 같은 대기가 발생하는 가장 큰 이유는 도서 배송 차량의 이동경로 및 도서 배송량 결정에 비효율성이 있기 때문이다. 이를 해결하기 위해 혼합정수계획모형이라는 수리적 모형을 통해 도서 배송량을 최대화할 수 있는 차량 경로이동 방법을 제시하였다. 그리고 실제 도서관의 상호대차 요구량 자료를 이용하여 하루 가용한 시간 별, 최적의 도서 이동 및 차량 경로 해법을 제안하였다.

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.

Persistent UAV delivery logistics: MILP formulation and efficient heuristic

Song, Byung Duk,Park, Kyungsu,Kim, Jonghoe Elsevier 2018 COMPUTERS & INDUSTRIAL ENGINEERING Vol.120 No.-

<P><B>Abstract</B></P> <P>The high efficiency, flexibility and low cost of Unmanned Aerial Vehicles (UAVs) present huge application opportunities in various industries. Among those various applications, we focus herein on the use of UAVs in delivery logistics. The UAV logistics system has some fundamental characteristics that distinguish it from the usual ground logistics such as limited flight time, loadable capacity, effect of cargo weight on flight ability, and others. To handle the above issues, we propose a Mixed Integer Linear Programming (MILP) formulation for derivation of persistent UAV delivery schedules. To address the computational issues, a Receding Horizon Task Assignment (RHTA) heuristic is developed and tested with numerical examples for island-area delivery.</P> <P><B>Highlights</B></P> <P> <UL> <LI> UAV delivery logistics with multiple recharge/reload stations was considered. </LI> <LI> UAVs visit station, refill consumables and return to service persistently. </LI> <LI> Amount of loaded product effects on the flight time of UAVs during delivery. </LI> <LI> Validity of the proposed model was demonstrated via island area delivery example. </LI> <LI> Performance of mathematical formulation and heuristic were tested and compared. </LI> </UL> </P>

정체를 고려한 Personal Rapid Transit 배차 및 경로 계획 알고리즘

한충균(Chung-Kyun Han),김백현(Baek-Hyun Kim),정락교(Rag-Gyo Jeong),하병현(Byung-Hyun Ha) 대한전기학회 2015 전기학회논문지 Vol.64 No.11

Personal rapid transit (PRT) is getting attention as a new form of transportation. It is energy efficient and provides the high level of passenger service. In this study, the dynamic PRT dispatching and routing problem is dealt with. Passengers request transportation service on a complex network, and an operating system monitors passenger arrivals and coordinates vehicles in real time. A new online dispatching and routing algorithm is proposed, which minimizes the total travel distance of vehicles and the waiting time of passengers. The algorithm dispatches vehicles by considering multiple vehicles’ state and multiple passengers at the same time. In particular, finding the shortest-time path is attempted by taking into account the future congestion on lanes. Discrete-event simulation is employed to validate the performance of the proposed algorithm. The results show the algorithm in this study outperforms others.