About

John Gunnar Carlsson is an associate professor at the University of Southern California in the Epstein Department of Industrial and Systems Engineering. He received his Ph.D. from the Institute for Computational and Mathematical Engineering at Stanford University in 2009 under the supervision of Yinyu Ye. His academic background also includes a Bachelor's degree in Mathematics and Music from Harvard College, earned in 2005. His research focuses on algorithms for solving problems in continuous location theory and more generally, optimization problems that involve geographic elements. His work is supported by various organizations including DARPA, the Office of Naval Research, the Air Force Office of Scientific Research, the National Science Foundation, and the Minnesota Department of Transportation, among others. Carlsson has received several awards, such as the 2016 Popular Science Magazine Brilliant Ten, the 2014 AFOSR Young Investigator Prize, and the 2013 INFORMS Computing Society Prize. He has also been recognized with departmental teaching awards and has held leadership roles, including serving as the Director of Program at the Daniel J. Epstein Institute.

Research topics

• Computer Science
• Artificial Intelligence
• Mathematics
• Algorithm
• Combinatorics
• Operations research
• Distributed computing
• Genetics
• Mathematical optimization
• Geodesy
• Discrete mathematics
• Operating system
• Manufacturing engineering
• Mechanical engineering
• Marketing
• Business
• Operations management
• Computer network
• Pure mathematics
• Computer vision
• Engineering
• Geography
• Biology
• Database

Selected publications

• A unified solution framework for truck-and-drone routing problems

  arXiv (Cornell University) · 2026-02-23

  articleOpen accessSenior author

  Coordinated truck-and-drone routing integrates the high capacity and range of ground vehicles with the flexible routing and speed of drones, enabling simultaneous service. Increasingly applied in last-mile delivery, this synchronization helps reduce completion time and operational costs. To improve its efficiency, various coordination modes between trucks and drones have been proposed. Each mode accommodates diverse operational constraints tailored to particular delivery requirements. In existing work, a slight change in the structural framework or operational characteristics could generate a totally different problem variant, which often requires the design of specialized algorithms. Consequently, under the requirement of maintaining structural validation and adapting to multiple operational features, this paper presents a unified three-phase solution framework based on the Lin-Kernighan-Helsgaun algorithm to solve a wide family of truck-and-drone routing problems. To validate its flexibility and effectiveness, we carry out numerical experiments on three problem variants: the Flying Sidekick Traveling Salesman Problem (FSTSP), the Traveling Salesman Problem with Multiple Drones (TSP-mD), and the Vehicle Routing Problem with Drones (VRP-D), benchmarking each against an effective algorithm. Computational results show that the framework can closely match optimal solutions on small-size instances and even improve the best-known solutions for several medium-size instances. Moreover, additional extensions are discussed to further highlight its versatility.

  PublisherOA PDF

• A unified solution framework for truck-and-drone routing problems

  Open MIND · 2026-02-23

  preprintSenior author

  Coordinated truck-and-drone routing integrates the high capacity and range of ground vehicles with the flexible routing and speed of drones, enabling simultaneous service. Increasingly applied in last-mile delivery, this synchronization helps reduce completion time and operational costs. To improve its efficiency, various coordination modes between trucks and drones have been proposed. Each mode accommodates diverse operational constraints tailored to particular delivery requirements. In existing work, a slight change in the structural framework or operational characteristics could generate a totally different problem variant, which often requires the design of specialized algorithms. Consequently, under the requirement of maintaining structural validation and adapting to multiple operational features, this paper presents a unified three-phase solution framework based on the Lin-Kernighan-Helsgaun algorithm to solve a wide family of truck-and-drone routing problems. To validate its flexibility and effectiveness, we carry out numerical experiments on three problem variants: the Flying Sidekick Traveling Salesman Problem (FSTSP), the Traveling Salesman Problem with Multiple Drones (TSP-mD), and the Vehicle Routing Problem with Drones (VRP-D), benchmarking each against an effective algorithm. Computational results show that the framework can closely match optimal solutions on small-size instances and even improve the best-known solutions for several medium-size instances. Moreover, additional extensions are discussed to further highlight its versatility.

  DOI

• Coordinated Logistics with a Truck and Multiple Sidekicks

  Transportation Science · 2026-04-17

  articleSenior author

  One of the more novel recent innovations in the logistics world, both in theory and in practice, is the use of small autonomous vehicles to facilitate last-mile delivery. One particular scheme that has received considerable recent attention is the “sidekick” scheme, in which a large cargo truck acts as a mobile “host” that deploys smaller vehicles such as aerial drones or unmanned ground vehicles (UGVs). In this paper, we develop a continuous approximation model that estimates the improvements to total completion time that such a system provides in the asymptotic limit as many demand points are drawn from a continuous probability distribution in the plane. Our key finding is that sidekick systems can be beneficial even when the sidekicks are slower than the host, provided there are sufficiently many of them. Funding: The authors gratefully acknowledge support from the Toyota University Research Program [ONR Grant N000142412277, DARPA Grant HR00112530234, and USC DOT Grant USC-DOT-913]. Disclaimer: The views expressed in this article are those of the author(s) and do not reflect the official policy or position of the U.S. Naval Academy, Department of the Navy, the Department of Defense, or the U.S. Government.

  PublisherDOI

• Individual and group fairness in geographical partitioning

  ArXiv.org · 2025-11-24

  preprintOpen access

  Socioeconomic segregation often arises in school districting and other contexts, causing some groups to be over- or under-represented within a particular district. This phenomenon is closely linked with disparities in opportunities and outcomes. We formulate a new class of geographical partitioning problems in which the population is heterogeneous, and it is necessary to ensure fair representation for each group at each facility. We prove that the optimal solution is a novel generalization of the additively weighted Voronoi diagram, and we propose a simple and efficient algorithm to compute it, thus resolving an open question dating back to Dvoretzky et al. (1951). The efficacy and potential for practical insight of the approach are demonstrated in a realistic case study involving seven demographic groups and $78$ district offices.

  PublisherOA PDFDOI

• A New Upper Bound for the Euclidean TSP Constant

  INFORMS journal on computing · 2025-09-05 · 1 citations

  article1st authorCorresponding

  Let [Formula: see text] be n independent and uniformly distributed random points in a compact region [Formula: see text] of area 1. Let [Formula: see text] denote the length of the optimal Euclidean traveling salesman tour that traverses all these points. The classical Beardwood-Halton-Hammersley theorem proves the existence of a universal constant [Formula: see text] such [Formula: see text] almost surely, which satisfies [Formula: see text]. This paper presents a computer-aided proof using numerical quadrature and decision trees that [Formula: see text]. Although our improvement is still somewhat small, our approach has the advantage that it is primarily limited by computer hardware and is thus amenable to further improvements over time. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the Office of Naval Research [Grants AWD-00008450, N00014-20-S-B001, and N00014-21-1-2208], the California Department of Transportation, and the U.S. Department of Transportation [Grant 69A3551747114]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0538 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0538 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

  PublisherDOI

• Redesigning Zoning Systems for Equitable and Efficient Last-Mile Delivery at Ninja Van

  INFORMS Journal on Applied Analytics · 2025-09-01

  article1st authorCorresponding

  We develop and implement a novel zoning optimization framework for Ninja Van, a major last-mile logistics provider in Southeast Asia. The framework integrates weighted Voronoi partitioning with vehicle routing under uncertain demand and varying vehicle capacities. Deployment of the system led to measurable gains in efficiency and equity, reducing delivery times and improving workload balance across stations.

  PublisherDOI

• A lossless a priori splitting rule for split-delivery routing problems

  ArXiv.org · 2025-04-04

  preprintOpen accessSenior author

  Resource allocation problems in which demand is splittable are usually solved using different solution methods from their unsplittable equivalents. Although splittable problem instances can be the easier of the two (for example, they might simply correspond to a linear relaxation of a discrete problem), there exist many problems, including routing problems, for which the converse is true. That is, the technology for solving unsplittable problems is mature, but the splittable counterpart is not. For such problems, one strategy that has recently shown potential is the use of an a priori splitting rule in which each customer's demand is split into smaller pieces in advance, which enables one to simply solve the splittable problem as an instance of the unsplittable version. An important factor to consider is the number of pieces that result after this splitting. A large numbers of pieces will allow more splitting patterns to be realizable, but will result in a larger problem instance. In this paper, we introduce a splitting rule that minimizes the number of pieces, subject to the constraint that all demand splitting patterns remain feasible. Computational experiments on benchmark instances for the vehicle routing problem and a time-windows extension show that the solution quality of our proposed splitting rule can match the performance of existing approaches.

  PublisherOA PDFDOI

• Code and Data Repository for A new upper bound for the Euclidean TSP constant

  INFORMS journal on computing · 2025-04-21

  articleSenior author

  This paper presents a computer-aided proof of a novel approach to constructing a new upper bound for the Euclidean Traveling Salesman Problem (TSP) Constant, leveraging numerical methods and decision trees. While the improvement achieved is modest, the approach offers a key advantage: it is primarily constrained by computer hardware, making it highly amenable to further optimization and advancements over time.

  PublisherDOI

• Demand Equilibria in Spatial Service Systems

  SSRN Electronic Journal · 2024-01-01

  articleOpen access1st authorCorresponding
  PublisherDOI

• Demand Equilibria in Spatial Service Systems

  Manufacturing & Service Operations Management · 2024-09-12 · 5 citations

  article1st authorCorresponding

  Problem definition: A service is offered at certain locations (“facilities”) in a geographical region. Customers can appear anywhere in the region, and each customer chooses a facility based on travel distance as well as expected waiting time. Customer decisions affect waiting times by increasing the load on a facility, and thus, they impact other customers’ decisions. The service provider can also influence service quality by adjusting service rates at each facility. Methodology/results: Using a combination of queueing models and computational geometry, we characterize demand equilibria in such spatial service systems. An equilibrium can be visualized as a partition of the region into service zones that form as a result of customer decisions. Service rates can be set in a way that achieves the best-possible social welfare purely through decentralized customer behavior. Managerial implications: We provide techniques for computing and visualizing demand equilibria as well as calculating optimal service rates. Our analytical and numerical results indicate that in many situations, resource allocation is a far more significant source of inefficiency than decentralized behavior. Funding: J. G. Carlsson was funded by the METRANS Transportation Consortium [Grant NCST-USC-RR-24-12] and the Office of Naval Research [Grant N00014-24-1-2277-P00001]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.0434 .

  PublisherDOI

Recent grants

• Using Computational Geometry to Solve Hard Mathematical Optimization Problems

  NSF · $291k · 2016–2021

Frequent coauthors

• Erik Carlsson

  9 shared

• Raghuveer Devulapalli

  6 shared

• Jianming Shi

  Lanzhou University Second Hospital

  5 shared

• Dongdong Ge

  5 shared

• Mehdi Behroozi

  5 shared

• Jung‐Fa Tsai

  National Taipei University of Technology

  4 shared

• Yi‐Chung Hu

  3 shared

• Benjamin Armbruster

  3 shared

Education

• Ph.D., Industrial and Systems Engineering

  University of Southern California

  1995

• M.S., Industrial and Systems Engineering

  University of Southern California

  1991

• B.S., Industrial and Systems Engineering

  University of Southern California

  1989

Awards & honors

• Popular Science Magazine Brilliant Ten (2016)
• AFOSR Young Investigator Prize (2014)
• INFORMS Computing Society (ICS) Prize (2013)
• INFORMS Junior Faculty Interest Group (JFIG) Paper Competiti…
• DARPA Young Faculty Award (2012)