Due to the complexity of urban area, the city vehicle routing problem has been a difficult problem. The problem has involved factors such as parking availability, road conditions, and traffic congestion, all of which increase transportation costs and delivery times. To resolve this problem, one effective solution can be the use of parcel lockers located near customer sites, where products are stored for customers to pick up. When a vehicle delivers products to a designated parcel locker, customers in the vicinity must pick up their products from that locker. Recently, identifying optimal locations for these parcel lockers has become an important research issue. This paper addresses the parcel locker location problem within the context of urban traffic congestion. By considering dynamic environmental factors, we propose a Markov decision process model to tackle the city vehicle routing problem. To ensure more real situations, we have used optimal paths for distances between two nodes. Numerical results demonstrate the viability of our model and solution strategy.
도서관은 문화 공간으로서 누구나 이용할 수 있고 다양한 분야의 지식과 정보를 제공하여 삶의 질을 높이는 중요한 사회기반 시설 중 하나이다. 현재 한국의 도서관 수는 수요에 비해 공급이 부족한 상황이며, 이를 해결하기 위해 일부 지자체는 차량을 수단으로 이동형 도서 서비스를 제공하는 분관 형태의 이동 도서관을 운영하고 있다. 주로 도서관을 이용하기 어려운 사람들을 대상으로 순회하며 도서관 서비스를 제공하지만, 비효율적인 운행 노선과 균일하지 않은 서비스로 실질적인 효과를 발휘하지 못하고 있다. 따라서 본 연구에서는 성남시 새마을 이동 도서관을 대상으로 순회 경로 현황을 파악하고, 최소 이동 거리로 개선된 이동 도서관 노선을 제시하고자 한다. 더욱 효율적인 운영을 위해 서비스 권역을 나누고, 시간 제약을 결합한 차량경로설정 문제를 사용하여 도서 서비스의 이용 격차를 줄인 새로운 운행 노선을 구축하였다. 본 연구는 이동 도서관의 효과적인 노선 운영에 대한 기초적인 자료로 활용될 수 있다는 점에서 의의가 있다. 향후 이동 도서관 뿐만 아니라 이동형 공공 서비스를 위한 유용하고 현실적인 가이드라인으로 활용될 수 있을 것이다.
Due to the issue of the sustainability in transportation area, the number of electric vehicles has significantly increased. Most automakers have decided or planned to manufacture the electric vehicles rather than carbon fueled vehicles. However, there are still some problems to figure out for the electric vehicles such as long charging time, driving ranges, supply of charging stations. Since the speed of growing the number of electric vehicles is faster than that of the number of charging stations, there are lack of supplies of charging stations for electric vehicles and imbalances of the location of the charging stations. Thus, the location problem of charging stations is one of important issues for the electric vehicles. Studies have conducted to find the optimal locations for the charging stations. Most studies have formulated the problem with deterministic or hierarchical models. In this paper, we have investigated the fluctuations of locations and the capacity of charging stations. We proposed a mathematical model for the location problem of charging stations with the vehicle routing problem. Numerical examples provide the strategy for the location routing problems of the electric vehicles.
Transportation in urban area has been getting hard to fulfill the demand on time. There are various uncertainties and obstacles related with road conditions, traffic congestions, and accidents to interrupt the on-time deliveries. With this situation, the last mile logistics has been a keen issue for researchers and practitioners to find the best strategy of the problem. A way to resolve the problem is to use parcel lockers. Parcel locker is a storage that customers can pick up their products. Transportation vehicles deliver the products to parcel lockers instead of all customer sites. Using the parcel lockers, the total delivery costs can be reduced. However, the inconvenience of customer has to increase. Thus, we have to optimal solution to balance between the total delivery costs and customers' inconvenience. This paper formulates a mathematical model to find the optimal solution for the vehicle routing problem and the location problem of parcel lockers. Experimental results provide the viability to find optimal strategy for the routing problem as well as the location problem.
The Dynamic Vehicle Routing Problem (DVRP) involves a combinatorial optimization problem where new customer demands become known over time, and old routes must be reconfigured to generate new routes while executing the current solution. We consider the high level of dynamism problem. An application of highly dynamic DVRP is the ambulance service where a patient contacts the service center, followed by an evaluation of case severity, and a visit by a practitioner/ ambulance is scheduled accordingly. This paper considers a variant of the DVRP and proposes a decentralized algorithm in which collaborators (Depot and Vehicle), both have only partial information about the entire system. The DVRP is modeled as a periodic re optimization of VRP using the proposed decentralized algorithm where collaborators exchange local information to achieve the best global objective for the current state of the system. We assume the existence of a dispatcher e.g., headquarter of the company who can communicate to vehicles in order to gather information and assigns the new visits to them. The effectiveness of the proposed decentralized coordination algorithm is further evaluated using benchmark data given in literature. The results show that the proposed method performed better than the compared algorithms which utilize the centralized coordination in 12 out of 21 benchmark problems.
After Dantzig and Rasmer introduced Vehicle Routing Problem in 1959, this field has been studied with numerous approaches so far. Classical Vehicle Routing Problem can be described as a problem of multiple number of homogeneous vehicles sharing a same starting node and having their own routes to meet the needs of demand nodes. After satisfying all the needs, they go back to the starting node. In order to apply the real world problem, this problem had been developed with additional constraints and pick up & delivery model is one of them. To enhance the effectiveness of pick up & delivery, hub became a popular concept, which often helps reducing the overall cost and improving the quality of service. Lots of studies have suggested heuristic methods to realize this problem because it often becomes a NP-hard problem. However, because of this characteristic, there are not many studies solving this problem optimally. If the problem can be solved in polynomial time, optimal solution is the best option. Therefore, this study proposes a new mathematical model to solve this problem optimally, verified by a real world problem. The main improvements of this study compared to real world case are firstly, make drivers visit every nodes once except hub, secondly, make drivers visit every nodes at the right time, and thirdly, make drivers start and end their journey at their own homes.
The vehicle routing problem is one of the vibrant research problems for half a century. Many studies have extensively studied the vehicle routing problem in order to deal with practical decision-making issues in logistics. However, developments of new logistics strategies have inevitably required investigations on solution methods for solving the problem because of computational complexity and inherent constraints in the problem. For this reason, this paper suggests a simulated annealing (SA) algorithm for a variant of vehicle routing problem introduced by a previous study. The vehicle routing problem is a multi-depot and multi-trip vehicle routing problem with multiple heterogeneous vehicles restricted by the maximum permitted weight and the number of compartments. The SA algorithm generates an initial solution through a greedy-type algorithm and improves it using an enhanced SA procedure with three local search methods. A series of computational experiments are performed to evaluate the performance of the heuristic and several managerial findings are further discussed through scenario analyses. Experiment results show that the proposed SA algorithm can obtain good solutions within a reasonable computation time and scenario analyses show that a transportation system visiting non-dedicated factories shows better performance in truck management in terms of the numbers of vehicles used and trips for serving customer orders than another system visiting only dedicated factories.
This research is to develop a possible process to apply k-means clustering to an efficient vehicle routing process under time varying vehicle moving speeds. Time varying vehicle moving speeds are easy to find in metropolitan area. There is a big difference between the moving time requirements of two specific delivery points. Less delivery times are necessary if a delivery vehicle moves after or before rush hours. Various vehicle moving speeds make the efficient vehicle route search process extremely difficult to find even for near optimum routes due to the changes of required time between delivery points. Delivery area division is designed to simplify this complicated VRPs due to time various vehicle speeds. Certain divided area can be grouped into few adjacent divisions to assume that no vehicle speed change in each division. The vehicle speeds moving between two delivery points within this adjacent division can be assumed to be same. This indicates that it is possible to search optimum routes based upon the distance between two points as regular traveling salesman problems. This makes the complicated search process simple to attack since few local optimum routes can be found and then connects them to make a complete route. A possible method to divide area using k-means clustering is suggested and detailed examples are given with explanations in this paper. It is clear that the results obtained using the suggested process are more reasonable than other methods. The suggested area division process can be used to generate better area division promising improved vehicle route generations.
The inventory routing problem (IRP) is an important area of Supply Chain Management. The objective function of IRP is the sum of transportation cost and inventory cost. We propose an Artificial Immune System(AIS) to solve the IRP. AIS is one of natural computing algorithm. An hyper mutation and an vaccine operator are introduced in our research. Computation results show that the hyper mutation is useful to improve the solution quality and the vaccine is useful to reduce the calculation time.
기간차량경로 문제는 차량용량제약을 고려한 차량경로문제를 다 기간으로 확장한 형태의 문제로 역방향 로지스틱스의 폐기물 혹은 재활용품 수거에 관련된 주요한 운영 문제들 중의 하나로 각 고객에 대해서는 계획기간 중에 방문해야 하는 횟수가 정해져 있어 방문날짜 조합을 결정해야 하며 주어진 방문날짜 조합 하에 각 기간의 차량경로도 결정해야 한다. 주요한 제약조건으로는 차량의 용량제약과 각 기간의 가용 시간제약이 있으며 소요차량의 대수를 최소화하는 것을 목적으
During last two decades the transportation system has developed into very intelligent system with GIS, GPS and ITS. The practical transportation management system provides real time response module to manage the customer's order. We have surveyed research papers on the real time vehicle routing problem in last two decades to figure out the dynamic vehicle routing problem. The papers are classified by basic routing algorithms and by managing the dynamic events which are the order management, the routing re-optimization, the routing post-optimization and the waiting strategy.
The vehicle routing problem determines each vehicle routes to find the transportation costs, subject to meeting the customer demands of all delivery points in geography. Vehicle routing problem is known to be NP-hard, and it needs a lot of computing time to get the optimal solution, so that heuristics are more frequently developed than optimal algorithms. This study aims to develop a heuristic method which combines guided local search with a tabu search in order to minimize the transportation costs for the vehicle routing assignment and uses ILOG programming library to solve. The computational tests were performed using the benchmark problems. And computational experiments on these instances show that the proposed heuristic yields better results than the simple tabu search does.
The main objective of this study is to find out the shortest path of the vehicle routing problem with time window constraints by using both genetic algorithm and heuristic. Hard time constraints were considered to the vehicle routing problem in this sug