Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe pickup and delivery problem with synchronized en-route transfers for microtransit planning
131
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Microtransit and other flexible transit fleet services can reduce costs by incorporating transfers. However, transfers are costly to users if they must get off a vehicle and wait at a stop for another pickup. A mixed integer linear programming model (MILP) is proposed to solve pickup and delivery problems with vehicle-synchronized en-route transfers (PDPSET). The transfer location is determined by the model and can be located at any candidate node in the network rather than a static facility defined in advance. The transfer operation is strictly synchronized between vehicles within a hard time window. A heuristic algorithm is proposed to solve the problem with an acceptable solution in a much shorter computation time than commercial software. Two sets of synthetic numerical experiments are tested: small-scale instances based on a 5x5 grid network, and large-scale instances of varying network sizes up to 250x250 grids to test scalability. The results show that adding synchronized en-route transfers in microtransit can further reduce the total cost by 10% on average and maximum savings can reach up to 19.6% in our small-scale test instances. The heuristic on average has an optimality gap less than 1.5% while having a fraction of the run time and can scale up to 250x250 grids with run times within 1 minute. Two large-scale examples demonstrate that over 50% of vehicle routes can be further improved by synchronized en-route transfers and the maximum savings in vehicle travel distance that can reach up to 20.37% for the instance with 100 vehicles and 300 requests on a 200x200 network.
rate research
Read More
The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows (VRPSPDTW) has attracted much research interest in the last decade, due to its wide application in modern logistics. Since VRPSPDTW is NP-hard and exact methods are only applicable to small-scale instances, heuristics and meta-heuristics are commonly adopted. In this paper we propose a novel Memetic Algorithm with efficient local search and extended neighborhood, dubbed MATE, to solve this problem. Compared to existing algorithms, the advantages of MATE lie in two aspects. First, it is capable of more effectively exploring the search space, due to its novel initialization procedure, crossover and large-step-size operators. Second, it is also more efficient in local exploitation, due to its sophisticated constant-time-complexity move evaluation mechanism. Experimental results on public benchmarks show that MATE outperforms all the state-of-the-art algorithms, and notably, finds new best-known solutions on 12 instances (65 instances in total). Moreover, a comprehensive ablation study is also conducted to show the effectiveness of the novel components integrated in MATE. Finally, a new benchmark of large-scale instances, derived from a real-world application of the JD logistics, is introduced, which can serve as a new and more challenging test set for future research.
In this study, we propose a three-stage framework for the planning and scheduling of high-capacity mobility-on-demand services (e.g., micro transit and flexible transit) at urban activity hubs. The proposed framework consists of (1) the route generation step to and from the activity hub with connectivity to existing transit systems, and (2) the robust route scheduling step which determines the vehicle assignment and route headway under demand uncertainty. Efficient exact and heuristic algorithms are developed for identifying the minimum number of routes that maximize passenger coverage, and a matching scheme is proposed to combine routes to and from the hub into roundtrips optimally. With the generated routes, the robust route scheduling problem is formulated as a two-stage robust optimization problem. Model reformulations are introduced to solve the robust optimization problem into the global optimum. In this regard, the proposed framework presents both algorithmic and analytic solutions for developing the hub-based transit services in response to the varying passenger demand over a short-time period. To validate the effectiveness of the proposed framework, comprehensive numerical experiments are conducted for planning the HHMoD services at the JFK airport in New York City (NYC). The results show the superior performance of the proposed route generation algorithm to maximize the citywide coverage more efficiently. The results also demonstrate the cost-effectiveness of the robust route schedules under normal demand conditions and against worst-case-oriented realizations of passenger demand.
Spacecraft investigations during the last ten years have vastly improved our knowledge about dust in the Jovian system. All Galilean satellites, and probably all smaller satellites as well, are sources of dust in the Jovian system. In-situ measurements with the dust detectors on board the Ulysses and Galileo spacecraft have for the first time demonstrated the electromagnetic interaction of charged dust grains with the interplanetary magnetic field and with a planetary magnetosphere. Jupiters magnetosphere acts as a giant mass-velocity spectrometer for charged 10-nanometer dust grains. These dust grains are released from Jupiters moon Io with typical rate of 1 kg s^1. The dust streams probe the plasma conditions in the Io plasma torus and can be used as a potential monitor of Ios volcanic plume activity. The other Galilean satellites are surrounded by tenuous impact-generated clouds of mostly sub-micrometer ejecta grains. Galileo measurements have demonstrated that impact-ejecta derived from hypervelocity impacts onto satellites are the major -- if not the only -- constituent of dusty planetary rings. We review the in-situ dust measurements at Jupiter and give an update of most recent results.
The Dynamic Pickup and Delivery Problem (DPDP) is aimed at dynamically scheduling vehicles among multiple sites in order to minimize the cost when delivery orders are not known a priori. Although DPDP plays an important role in modern logistics and supply chain management, state-of-the-art DPDP algorithms are still limited on their solution quality and efficiency. In practice, they fail to provide a scalable solution as the numbers of vehicles and sites become large. In this paper, we propose a data-driven approach, Spatial-Temporal Aided Double Deep Graph Network (ST-DDGN), to solve industry-scale DPDP. In our method, the delivery demands are first forecast using spatial-temporal prediction method, which guides the neural network to perceive spatial-temporal distribution of delivery demand when dispatching vehicles. Besides, the relationships of individuals such as vehicles are modelled by establishing a graph-based value function. ST-DDGN incorporates attention-based graph embedding with Double DQN (DDQN). As such, it can make the inference across vehicles more efficiently compared with traditional methods. Our method is entirely data driven and thus adaptive, i.e., the relational representation of adjacent vehicles can be learned and corrected by ST-DDGN from data periodically. We have conducted extensive experiments over real-world data to evaluate our solution. The results show that ST-DDGN reduces 11.27% number of the used vehicles and decreases 13.12% total transportation cost on average over the strong baselines, including the heuristic algorithm deployed in our UAT (User Acceptance Test) environment and a variety of vanilla DRL methods. We are due to fully deploy our solution into our online logistics system and it is estimated that millions of USD logistics cost can be saved per year.
This paper presents a solution to Autonomous Underwater Vehicles (AUVs) large scale route planning and task assignment joint problem. Given a set of constraints (e.g., time) and a set of task priority values, the goal is to find the optimal route for underwater mission that maximizes the sum of the priorities and minimizes the total risk percentage while meeting the given constraints. Making use of the heuristic nature of genetic and swarm intelligence algorithms in solving NP-hard graph problems, Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) are employed to find the optimum solution, where each individual in the population is a candidate solution (route). To evaluate the robustness of the proposed methods, the performance of the all PS and GA algorithms are examined and compared for a number of Monte Carlo runs. Simulation results suggest that the routes generated by both algorithms are feasible and reliable enough, and applicable for underwater motion planning. However, the GA-based route planner produces superior results comparing to the results obtained from the PSO based route planner.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
