Scenario A

The roads in your hometown are in poor condition, and budget limitations on repairs, as well as lack of staff and machinery, are making it hard to carry out all the repairs at once. Even finding out where repairs are needed is a problem. Riding around town looking for potholes is not efficient, and relying on volunteer residents to report potholes tends to produce biased claims about which holes should be prioritized.

a pothole in the pavement

Photograph linked from Wikimedia and reused with Creative Commons licence.

You have an idea for a road-monitoring project. A small fleet of municipal vehicles, such as park maintenance vehicles and garbage trucks, is at your disposal. Postal delivery vehicles might also be available. You could equip these vehicles with a device that would gather data about the condition of the pavement and then feed the data into a semi-automated decision-support system. This system would advise on where and when to send pavement repair teams to fix potholes and cracks before anyone gets hurt.

Phase 1

Morning, team. We've gotten some complaints about the garbage trucks not picking up the garbage when passing while the truck was actually on its way to someplace else and not on route for pick-up. Could we work on updating the routes to minimize the chances of this happening?

Week after week, while trying to keep up with an ever-increasing workload, you keep thinking about your road-monitoring idea. Is there a way you can turn your idea into a concrete plan while also delivering solutions to the immediate needs that will satisfy your superiors?

Hands-on option

Basic stage for the hands-on option

Propose a metaheuristic that will create weekly routes for a fleet of k vehicles that avoid transiting on streets where vehicles do not have designated pick-ups. It is preferable for vehicles to only use routes where they have pickups as much as possible. Sketch out a constructive phase for a feasible initial solution and a local-search phase for improved optimality.

You do not have to implement anything in code (unless you really want to). You can use either text or pseudocode (or a combination of both) to describe your proposal.

In-depth stage for the hands-on option

Explore and discuss possible performance measures for assessing whether the routes that the heuristic can produce are any good.

Conceptual option

Basic stage for the conceptual option

Browse through a few chapters of Smart Delivery Systems: Solving Complex Vehicle Routing Problems. Come up with a list of about a dozen terms that seem frequent or fundamental to formulating vehicle-fleet routing problems. Start by loosely defining the terms in your own words.

In-depth stage for the conceptual option

Once you have completed your definitions, take a look at Green Transportation and New Advances in Vehicle Routing Problems. Compile a brief list of any additional aspects (additional, modified objectives or restrictions) relevant to the formulation of a vehicle-fleet routing problem while taking sustainability into consideration.