This project presents two approaches to this problem: a customized matching algorithm and linear optimization.  Both approaches are presented because where the linear optimization clearly allows more trucks obtain new positions, a customized matching algorithm allows more generation of output within a single script.  In addition, this project will present a web interface that allows food trucks to enter preference data that in turn can be used by the trading algorithms in order to create new schedule.

Matching Algorithm Approach

The key features to the customized matching algorithm are that it allows and shows trades between two or more food trucks, and only considers food trucks whose preferences are available.  Therefore, all trucks involved in any given trade loop have location/day preferences that are other trucks’ location/day assignments.  This guarantees that a trade will be converged upon.

Linear Optimization Approach

The LP approach solves by trying to maximize the number of preferred spots assigned to each truck. Constraints are added that prevent any truck from being worse off, i.e. a truck can only receive as an assignment either a preferred spot or what they were initially assigned in the lottery. Additional constraints ensure that the number of trucks assigned to a given location does not exceed the MRV capacity allowed at that location, and all trucks end with a number of spots equal to what the entered with (this enforces the one for one trading rule). The preference data is preprocessed to make sure that no truck enters preferences for a day block in which they are certain to receive an assignment.

Comparison of Approaches

Both the Linear Optimization and Matching Algorithm are useable, expandable, and available via free software.  The Linear Optimization truly allows more trucks to be assigned their preferences, provided that they are trading a location/day assignment, because it looks not only to assign trucks their preference based on what other trucks are trading, but also looks to fill the capacity of each MRV location. 

The matching algorithm does not assign as many trucks their preferences as the linear optimization, but it does still have good results with seven out of ten trucks receiving preferred location/day assignments.  The matching algorithm also strictly abides by the current DCRA regulations, in that the only way a truck can obtain a preferred location/day assignment is by trading with another truck.  The matching algorithm also outputs the trades that it makes, allowing the DCRA to physically approve each trade that is made.