A professor uses geometry to solve the toughest logistical problems

The U.S. Air Force, the U.S. Department of Transportation, and the Boeing Company have sought John Gunnar Carlsson's distinct approach.
Deena Theresa
John Gunnar Carlsson uses geometry to solve complex vehicle routing challenges.Asia-Pacific Images Studio/iStock

Associate Professor John Gunnar Carlsson recalls being an impatient child.

"I hated waiting in line for things. And that influenced the kind of work I do now," he told IE in a video interview.

Carlsson's work entirely focuses on making logistics processes, like routing vehicles or using drones to deliver packages more efficiently. "That impatience and the need to get things done quickly and efficiently is a big part of how I make decisions in my life and what I like to work on," he says.

Oh well, that's not too hard, is it?

Hold your horses. It involves math.

Allow me to illustrate.

Amid the construction of the San Francisco 49ers' new 68,000-seat stadium, the team wanted more clarity on the most efficient routes to be taken in order to deliver hot dogs to fans' seats pronto. 

Carlsson came to their rescue. He developed an algorithm for estimating waiting times for “in-seat delivery” at the new stadium. The innovative service involved a person seated inside the stadium placing an order on their mobile phone, which was delivered within a short time.

Currently, the Kellner Family Associate Professor of Industrial and Systems Engineering at the University of Southern California, Carlsson works on algorithms for solving problems in continuous location theory and "optimization problems with a geographic element". 

A professor uses geometry to solve the toughest logistical problems
John Gunnar Carlsson.

Employing geometry for efficiency

Why is this important?

"Efficiency is certainly important, but that extends to a lot of aspects of life: For example, you could reduce your carbon footprint by using a more efficient vehicle route or figure out the best way to route vehicles to take pictures of a city so that people can see scenery they've never been to. Or you could deliver food, groceries, or gas to people with mobility problems who have difficulty leaving their homes," says Carlsson.

Okay...but what's his modus operandi?

Rather than considering the most efficient sequence of places to visit, Carlsson's favorite question to ask is, "how should you partition a territory into pieces to make the routes have a nice 'shape'?"

Didn't think of it that way, did you?

Geometry is Carlsson's weapon of choice. Using one of the oldest branches of mathematics, he has solved distribution problems for the top guns, namely the Air Force Office of Scientific Research, the National Science Foundation, the U.S. Department of Transportation, and the Boeing Company.

Symbiotic routing with little robots

Recently, his research proposal on Symbiotic Vehicle Routing was one of three projects selected to receive funding through The Raymond Corporation University Research Program

"I like to study problems that involve transportation and logistics. What I'm most excited about is when it involves new technology that brings a set of new challenges that we haven't thought of. The idea of symbiotic vehicle routing involves trucks or vehicles of any kind that have to drop off and deliver packages. What's new about this is that now those vehicles have little tiny helper vehicles that work with them," says Carlsson.

According to the research paper, a symbiotic vehicle routing scheme is a logistical framework in which a large vehicle, such as a truck, serves as a mobile "host" for a fleet of small "helper" vehicles, such as aerial drones.

"Several companies, like the US Postal Service and Mercedes, [are exploring the use of] delivery vans with drones that sit on top of them. The van drives through the street, and then the drone picks up a package and drops it off at someone's doorstep. The van and the drone are working together - resulting in what's called symbiotic reading. And they're helping each other to fulfill this mission. But here, you could replace the drones with little robots on the ground," he explains.

Using drones to deliver things comes with a different set of challenges. "People aren't very comfortable with the thought of drones flying over their heads. The symbiotic routing here could refer to the general case - not just flying," he says.

Carlsson then creates algorithms for these routing systems. 

"We have three areas that we want to study and exploit features [of]. The first would be a crowded city and the second would be a more rural area or the countryside, as it has a different kind of road network. The third would be the insides of a warehouse wherein you would have a giant forklift or a similar machine that carries things and little helper robots that move it around and help it pick up smaller things. We could then get things out the door more efficiently by using pickers this way," Carlsson explains.

A professor uses geometry to solve the toughest logistical problems
A self-driving delivery van and robot. Source: Chesky_W/iStock

Music to math, not a natural course

Carlsson's father is a Mathematician. Well, that makes sense, you may think. Not quite. Though he introduced the young Carlsson to geometric toys such as the Mobius strip, Carlsson was drawn toward music and wanted to pursue it at university.

Two years into his course at Harvard, he realized that the academic way of learning music wasn't his thing. "I thought I'd learn math instead, as I'd already liked it. I took a course called mathematical modeling, wherein you learn math to make models of things in the real world. We learned how to model the movement of smoke in the atmosphere, the spread of disease, gravitational forces, etc," he says.

And as his final project, Carlsson wanted to try working on a mathematical model of how a post office works.

"In a post office, efficiency is extremely important. I wanted to explore the queueing theoretic analysis in a post office to try to figure out if they could improve their efficiency. [Queuing theory is a branch of mathematics that studies how lines form, how they function, the size of the line required for a given service, why they malfunction and lead to long wait times, etc.] The results said that it could be improved by 10 percent. And I thought this is exactly what I wanted to do - use math to optimize human processes," explains Carlsson.

Based on his positive experience with operations research, he then went on to Standford for his Ph.D. research, which Boeing funded.

Solving complex challenges

Carlsson says the projects he conducted for the Air Force and Boeing were very similar. 

Picture this. Dividing a city into smaller pieces in an optimal manner so that they can be connected by the shortest distances possible. 

"That's a hard problem because you're trying to optimize not just an equation, but you have to figure out what the boundary between different regions should be - this is called an infinite-dimensional problem. And in the case of Boeing, I'd divide a piece of land into smaller ones to distribute a bunch of vehicles. We ended up using the ham sandwich theorem for that one," he says.

[The Ham Sandwich Theorem states that, given ham and two slices of bread positioned together in any configuration, it is always possible to slice the sandwich with a single cut so that the ham and bread are all divided into equal halves.]

Carlsson reveals his methodology for solving many of these complex logistics problems.

"It's called the continuous approximation method. Sometimes you can have a very complicated routing optimization problem. I could have a million customers that I have to visit and deliver packages to, and computing those routes can be very difficult. But even without solving it, you can predict how much it could cost you," Carlsson explains.

[The continuous approximation method is an efficient technique for modeling complex logistics problems.]

Another approach he uses is computational geometry, which involves designing, analyzing, and implementing algorithms for solving geometric input and output problems. It is fundamentally based on data structures and algorithms on points or line segments in space.

Miles to go

"I'm very interested in studying random stow [A process in which items are unloaded wherever there is space in a warehouse and then scanned into a computer system that can track where the item is located]. To humans, random stow is completely chaotic. There are a lot of math questions there about how you can solve these problems...I don't think they have been addressed yet," he says.

Carlsson is also excited by topological data analysis.

"It studies the shape of very high dimensional data. I think it's very promising and exciting, and I'm looking forward to finding a way to use it in the next problems that I work on," he says.

I asked him the one thing he would want to tell our readers.

"If you like math, give operations research a try! It's a lot of fun," he adds.

Add Interesting Engineering to your Google News feed.
Add Interesting Engineering to your Google News feed.
message circleSHOW COMMENT (1)chevron
Job Board