Explanipedia

On the Hardness of the Drone Delivery Problem Open

Simon Bartlmae, Andreas Hene, Kelin Luo · 2025

Fast shipping and efficient routing are key problems of modern logistics. Building on previous studies that address package delivery from a source node to a destination within a graph using multiple agents (such as vehicles, drones, and sh…

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously Open

Matthias Kaul, Kelin Luo, Matthias Mnich, Heiko Röglin · 2025

We study the problem of partitioning a set of $n$ objects in a metric space into $k$ clusters $V_1,\dots,V_k$. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric…

Connected k-Center and k-Diameter Clustering Open

Lukas Drexler, Jan Eube, Kelin Luo, Dorian Reineccius, Heiko Röglin , et al. · 2024

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem . The former problem has been introduced by Ge et al. (ACM Trans Knowl Discov Data 2(2):1–35, 2008. https://doi.org/10.1…

Online car-sharing problem with variable booking times Open

Haodong Liu, Kelin Luo, Yinfeng Xu, Huili Zhang · 2024

In this paper, we address the problem of online car-sharing with variable booking times (CSV for short). In this scenario, customers submit ride requests, each specifying two important time parameters: the booking time and the pick-up time…

Connected k-Center and k-Diameter Clustering Open

Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt , et al. · 2023

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side cons…

A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem Open

Kelin Luo, Alexandre M. Florio, Syamantak Das, Xiangyu Guo · 2022

Ride-sharing is an essential aspect of modern urban mobility. In this paper, we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity stat…

Package Delivery Using Drones with Restricted Movement Areas Open

Thomas Erlebach, Kelin Luo, Frits Spieksma · 2022

For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider …

Solving large-scale dynamic vehicle routing problems with stochastic requests Open

Jian Zhang, Kelin Luo, Alexandre M. Florio, Tom Van Woensel · 2022

The online food delivery problem on stars Open

Xiangyu Guo, Kelin Luo, Zhihao Gavin Tang, Yuhao Zhang · 2022

We introduce the Online Food Delivery Problem (OFDP) to model the delivery problem commonly encountered in online food-ordering-and-delivery platforms. In the OFDP the requests (orders) are submitted online, and the depot (restaurant) need…

Car-sharing between two locations: Online scheduling with flexible advance bookings Open

Kelin Luo, Thomas Erlebach, Yinfeng Xu · 2022

We study an online scheduling problem that is motivated by applications such as car-sharing. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using a single server (car). Each ride request speci…

The Multi-vehicle Ride-Sharing Problem Open

Kelin Luo, Chaitanya Agarwal, Syamantak Das, Xiangyu Guo · 2022

Ride-sharing is one of the most popular models of economical and eco-friendly transportation in modern smart cities, especially when riding hybrid and electric vehicles. Usually multiple passengers with similar itineraries are grouped toge…

Minimizing Travel Time and Latency in Multi-Capacity Ride-Sharing Problems Open

Kelin Luo, Frits Spieksma · 2022

Motivated by applications in ride-sharing and truck-delivery, we study the problem of matching a number of requests and assigning them to cars. A number of cars are given, each of which consists of a location and a speed, and a number of r…

Minimizing the Maximum Flow Time in the Online Food Delivery Problem Open

Xiangyu Guo, Shi Li, Kelin Luo, Yuhao Zhang · 2022

We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the order. Specifically, we study a problem where k vehicles of …

Online Bin Packing with Overload Cost Open

Kelin Luo, Frits Spieksma · 2021

In the classical online bin packing problem, items arriving one by one with a given size not greater than 1 must be packed into unit-capacity bins such that the total size of items packed in a bin does not exceed its capacity; the objectiv…

Online scheduling of car-sharing request pairs between two locations Open

Kelin Luo, Yinfeng Xu, Haodong Liu · 2020

We consider an online car-sharing problem between two locations with advance bookings. Each customer submits a pair of requests, where each request specifies the pick-up time and the pick-up location: one request from A to B , and the othe…

Approximation algorithms for car-sharing problems Open

Kelin Luo, Frits Spieksma · 2020

We consider several variants of a car-sharing problem. Given are a number of requests each consisting of a pick-up location and a drop-off location, a number of cars, and nonnegative, symmetric travel times that satisfy the triangle inequa…

Two Moves per Time Step Make a Difference Open

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, Jakob T. Spooner · 2019

A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves ov…

Car-Sharing on a Star Network: On-Line Scheduling with k Servers Open

Kelin Luo, Thomas Erlebach, Yinfeng Xu · 2019

We study an on-line scheduling problem that is motivated by applications such as car-sharing for trips between an airport and a group of hotels. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit …

Car-Sharing Between Two Locations: Online Scheduling with Flexible Advance Bookings Open

Kelin Luo, Thomas Erlebach, Yinfeng Xu · 2018

Car-Sharing between Two Locations: Online Scheduling with Two Servers Open

Kelin Luo, Thomas Erlebach, Yinfeng Xu · 2018

In this paper, we consider an on-line scheduling problem that is motivated by applications such as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using two servers (cars)…

Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings Open

Kelin Luo, Thomas Erlebach, Yinfeng Xu · 2018

We study an on-line scheduling problem that is motivated by applications such as car-sharing, in which users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request …

Kelin Luo YOU? Author Swipe