The classic "traveling salesperson problem" in mathematics asks: Given a list of cities and the distances between each pair of cities, what is the shortest possible route for the salesperson to visit each city exactly once and return to the origin city?
Davidson students in a community-based learning "Mathematical Modeling" course recognized that this theoretical exercise had real world consequences for the non-profit Charlotte Community ToolBank. The organization maintains a vast inventory of tools, from cordless drills, ladders, rakes and shovels to circular saws, and makes them available to local charitable organizations for their community service projects.
Clients include churches, scout troops and community initiatives such as Hands On Charlotte and Great American Clean-Up. Last year the four-year-old ToolBank processed 527 tool orders, and expects to exceed that figure this year. All area non-profits are eligible to register to use the service, and pay just three percent of the retail price of each tool per week as a handling fee.
But while their mission is admirable, ToolBank systems needed help. With a total of 11,000 tools located in scores of bins around its 5,500-square-foot warehouse, volunteers who assembled tool orders wasted a lot of time and shoe leather in "scavenger hunts" around the warehouse for the exact items clients needed.
"We were looking for ways to make the process more efficient," said ToolBank program manager Sheri Osborne.
Davidson students Julie Park '16, Ross Kruse '17 and Katy Williams '17 were coincidentally enrolled in last semester's "Mathematical Modeling" course. For one of their assignments, Kimbrough Professor of Mathematics Laurie Heyer required students to identify and address an issue faced by the college or a local nonprofit organization.
Park, a Presidential Scholar, had earlier joined friends in a day of volunteer service at the Charlotte Community ToolBank where she learned about the organization's problems assembling orders. She asked Osborne if she, Kruse, who is a Julian and Robert J. Lake Scholar, and Williams could work on it as their course project. Osborne was delighted.
"It's awesome to have someone outside of ToolBank look at our situation with fresh eyes," she said.
Williams said her group's original plan was to rearrange the tools in the warehouse. "But the shelves and boxes are big and heavy, and it would be inefficient to rearrange everything. So instead we took a Google map approach, and used Dijkstra's algorithm for finding the shortest paths between nodes in a graph, and the Nearest Neighbor approach to ordering the nodes."
She continued, "We mapped the location of 41 tool storage points in the warehouse and fed those into the system. Now volunteers get a printout that shows them not only the number and type of tools requested, but also their location, and the quickest path to reach all those locations. Basically, it's solving the Traveling Salesperson problem."
The Davidson students spent about a month developing and testing the program, which they named the "Charlotte Community ToolBank Order Helper." In addition to mapping the location of tools, they assigned a "grabability" index for each tool that reflected the particular difficulty of carrying large, heavy items.
While Williams, Kruse and Park focused their efforts on Charlotte Community ToolBank, other groups of students in Heyer's class focused on campus projects. They included a more efficient system to schedule tutors in the math and science center, a more efficient system to assign the 100 or so Orientation Team students to tasks during the annual 10-day orientation period, and an approach to decreasing food waste at Vail Commons.
Williams and Heyer are continuing the initiative this summer by working together on a project called PRONTO (Productive Online Tools). It includes a system to help students find classes that meet their curriculum requirements, and a program to track faculty work on department and campus-wide committees.
Heyer's community-based learning course in math modeling is among nearly 20 such courses offered each year in disciplines throughout the curriculum. Coordinated through the college's Office of Civic Engagement, the program stipulates that each course must include work on a community-defined need.
Heyer will again offer "Mathematical Modeling" in the spring 2016 semester. Community-based learning courses offered in the upcoming fall semester include "Medical Anthropology," "Food and Sustainability" and "Life Stories."
Heyer said her course and other community-based learning courses are popular with students because they allow them to "do something real and meaningful, and contribute to the life of the college and beyond."
Williams has spent part of her summer on campus working on the final details of Charlotte Community ToolBank Order Helper. Pleased with her work, the ToolBank staff has asked her to consider helping to improve the ToolBank's nationwide LFNt (pronounced "Elephant") inventory system.
The national organization, comprised of nine affiliates, plans this summer to launch a $180,000 fundraising campaign to improve LFNt. But what she really needs, said Osborne, is another smart, dedicated Davidson College student who could integrate LFNt with the Charlotte Community ToolBank Order Helper.
"Would she be interested?" Osborne asked Williams at a recent meeting. The national ToolBank information/technology committee will be considering the upgrade in the early fall, and Osborne would love to have Williams sitting at the table.