Optimization
Home Schedule Projects Evaluation and Policy Resources Announcements
Projects

Team-based projects are integrated as an essential part of the course. These projects help students to get hands-on experience in applying different metaheuristic technqiues studied in this course in solving combinatroial problems. Students select one of the problems listed below for which they will undertake an independent investigation and apply the studied algorithms in the course to solve it. Course instructor and TAs will provide support to help the students with searching and using the literature, analyzing the challenging aspects of the problem and writing the final report of the project. The programming parts of the project must be implemented in Matlab/Octave.

Projects MUST be done in group of 5 students. Teamwork helps to achieve more than what could ever be achieved on your own, improve problem solving, foster creativity and innovation and improve decision making. Teams of students must conceive, design and develop the project. Different issues should be considered to form a collaborative team such as responsibility for assignment, team composition (hard and soft skills, previous academic performance, etc.) and the schedule of the team members (how easy to establish regular face-to-face meetings). Once team is formed, students should be willing to subordinate their personal preferences to the decisions of the team, and be willing to compromise in order to achieve a group consensus. As team work should have team rewards, team members will receive a common grade. However a free-riding team member will be penalized if a common and repetitive negative feedback (peer evaluations) received from the other team members. This feedback will be investigated before deciding the penalty.

Best projects will be recommended for publication as journal papers in special issues of International Journal of Unmanned Systems Engineering and International Journal of Robotics and Automation about Stochastic Optimization Techniques for Unmanned Systems.

The following is the definite list of projects. Registration is on a first come, first served basis. To register, please fill in the registration form before Friday May 22, 2015 and submit it to your course instructor's email address. Please check below the registration status before selecting the project.

List of available projects:
ID
Project title and description Assignement
1
Vehicle Suspension Design: The primary function of a suspension system of a vehicle is to isolate the road excitations experienced by the tires from being transmitted to the passengers. This design problem can be seen as an optimization problem with two objectives: minimizing the maximum bouncing acceleration of the sprung mass and minimizing average suspension displacement subject to a number of constraints. The constraints arise from the practical kinetic and comfortability considerations, such as limits of the maximum vertical acceleration of the sprung mass and the suspension working space. For more details [A.E. Baumal, J.J. McPhee, P.H. Calamai, “Application of genetic algorithms to the design optimization of an active vehicle suspension system ,” Computer Methods in Applied Mechanics and Engineering, Volume 163, Issues 1–4, 21 September 1998, Pages 87–94.]

 

2
Overhauling Gas Turbine Engines: To guarantee a uniform gas flow through the turbines there are nozzle-guide vane assemblies located at each turbine stage. Such an assembly basically consists of a number of nozzle guide vanes affixed about its circumference. All these vanes have individual characteristics and the correct placement of the vanes can result in substantial benefits (reducing vibration, increasing uniformity of flow, reducing fuel consumption). The problem of placing the vanes in the best possible way can be modeled as a TSP with a special objective function. Ref. [Plante, R.D.; T.J. Lowe & R. Chandrasekaran (1987). The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristics. Operations Research, Vol. 35, pp.772-783.].  
3
Wildlife Corridor Design: Protecting wildlife corridors is a conservation strategy where connectivity is explicitly: preserved by protecting enough land to form a contiguous corridor between areas of biological significance. Specifically, in the wildlife corridor design problem, we are given a set of land parcels, a set of reserves (land parcels that correspond to biologically significant areas), and the cost (e.g., land value) and utility (e.g., habitat suitability) of each parcel. The goal is to select a subset of the parcels that forms a connected network, including all reserves. Conservation and land use planners generally operate on a limited budget, while striving to secure the land that results in the corridor with best habitat suitability. This problem is an instance of the so-called budget-constrained Steiner connected subgraph problem with node profits and node costs, where the nodes correspond to parcels, the terminal nodes correspond to the reserves, and the edges correspond to adjacency of parcels [Bistra Dilkina. Exploiting Structure in Combinatorial Problems with Applications in Computational Sustainability. PhD. Thesis, Cornell University , 2012].  
4

Improving Landscape Connectivity: Another strategy used in conservation is to improve landscape connectivity without necessarily requiring the conservation of complete corridors. Ecologists have developed models of landscape resistance that capture the difficulty or probability of movement of a species individual from one location to another in a habitat matrix. The landscape is represented as a set of small parcels or pixels, each of which has a resistance value that gives the species-specific cost of moving through particular landscape features. The resistance surface depends on both the focal species and the actual landscape characteristics. Resistance models are inferred by relating landscape characteristics to genetic distance between individuals of the species at different locations or to radio-collar movement data. The benefit of buying a piece of land is reflected in a reduction in the land’s effective resistance through conservation management. Under the least-cost path model used in ecology, the connectivity between two designated habitat patches or locations is measured as the length of the shortest resistance-weighted path between them. In the landscape connectivity conservation problem, given pairs of important habitat patches (i.e., existing conserved areas or areas with an established subpopulation of the species) and a budget limit, the goal is to select a subset of parcels for conservation management that minimizes the sum over the pairs of important patches of the length of the shortest resistance-weighted path, thereby maximizing the resulting landscape connectivity [Bistra Dilkina. Exploiting Structure in Combinatorial Problems with Applications in Computational Sustainability. PhD. Thesis, Cornell University , 2012].

 
5
Wind Park Design Problem: This project addresses the problem associated with the optimal wind park design. A combinatorial optimization model for wind turbines type and number choice and placement considering the given wind conditions and wind park area will be developed. Ref.: [Ivan Mustakerov and Daniela Borissova, "Wind turbines type and number choice using combinatorial optimization", Renewable Energy 35 (2010) 1887-1894][Andrew Kusiak, Zhe Song, "Design of wind farm layout for maximum wind energy capture," Renewable Energy 35 (2010) 685–694].  
6
Elevator Dispatching Problem: Elevator dispatching is a good example of a stochastic optimal control problem of economic importance that is too large to solve by classical techniques such as dynamic programming. The objective of elevator dispatching is to provide passengers with the shortest waiting times and the shortest time to destination. Ref.: [Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press] and [Berna Bolata, Pablo Cortés, “Genetic and tabu search approaches for optimizing the hall call—Car allocation problem in elevator group systems,” Applied Soft Computing 11 (2011) 1792–1800.]  
7
The Capacitated Vehicle Routing Problem: The CVRP is a very basic formulation of a problem which a transportation company may face in its everyday operations. The goal is to find the shortest-possible set of routes for the company’s vehicles in order to satisfy demands of customers for certain goods. Each of identical vehicles starts and finishes its route at the company’s depot, and must not carry more goods than its capacity specifies. All customers have to be serviced, each exactly once by one vehicle. Distances between the depot and customers are given. The version of CVRP considered here does not fix the number of vehicles (it is a decision variable); also the distance to be travelled by a vehicle is not constrained. [Marek Kubiak, "Distance Measures and Fitness-Distance Analysis for the CVRP," Chapter 18 in ]. Raphael Dorne, Patrick Mills and Chris Voudouris, "Solving Vehicle Routing using iOpt," Chapter 20 in in Metaheuristics Progress in Complex Systems Optimization, Springer, 2007].  
8
School Bus Routing Problem: The objective of the scheduling is to obtain a bus loading pattern such that the number of routes is minimized, the total distance travelled by all buses is kept at minimum, no bus is overloaded and the time required to traverse any route does not exceed a maximum allowed policy. For problem modeling, see [Angel, R.D.; Caudle, W.L.; Noonan, R. & Whinston, A. (1972). Computer assisted school bus scheduling. Management Science, Vol. 18, pp.279–88.], [Michela Spada, Michel Bierlaire, Thomas Liebling, "Decision-aid Methodology for the School BusRouting and Scheduling Problem," STRC 3rd Swiss Transport Research Conference Monte Verita / Ascona, March 19-21, 2003] and Yindong Shen . Tabu Search for Bus and Train Driver Scheduling. PhD Thesis, The University of Leeds, 2001.  
9
Dynamic Location Problem: Consider that there are n clients, m facilities’ possible locations, and T time periods considered in the planning horizon. A facility can be opened, closed and reopened more than once during the planning horizon. A general model must consider two different types of facilities: 1-uncapacitated facilities; 2- facilities with maximum and/or minimum capacity restrictions. The objective function considers the minimization of all fixed costs and transportation costs. The fixed costs account for the opening, closure and fixed operating costs during the operating time periods. The model assures that each client’s demand in each time period has to be satisfied; each client can only be assigned to operating facilities. A facility can only be reopened at the beginning of period t if it has been opened earlier and can only be opened once during the planning horizon. Only one facility can be open at each location, in each time period. It is possible to extend this problem to the multi-level case, where a client has to be assigned to a path of facilities, instead of only one facility. A path of facilities can be constituted of, at most, k facilities (where k represents the maximum number of levels considered), and, at most, one facility of each level [Joana Dias, M. Eugénia Captivo and João Clímaco, "A Memetic Algorithm for Dynamic Location Problems," Chapter 12 in in Metaheuristics Progress in Complex Systems Optimization, Springer, 2007].  
10
Railway Timetable Problem: A practical description of ailway timetable problem (RTP) is as follows: Given a certain rail infrastructure, and given a certain required service of trains, can the infrastructure provide this service without conflicts?. The typical RTP revolves around the question of which set of departure times (timetable) of trains causes no conflicts between trains while they are traveling on a railroad infrastructure. The infrastructure (the problem domain) is a resource-constrained network; trains tend to share tracks at some point, and an ideal timetable would prevent trains from hindering each other during service. The railway timetable problem can be extended by including other variables, such as waiting time for passengers, the availability of carriages and personnel at stations at a given time, and so on. The form of the railroad infrastructure plays an important role in the complexity of the problem domain. Some countries can develop a tree-structure which can reduce the complexity significantly.Many densely populated countries with old railway infrastructures, such as in the Netherlands, have to work with dense networks that contain many cycles. Besides the infrastructure, usually some other aspects of the problem domain are known as well, such as the allowed speeds of the trains in different situations, the minimal (and often also the maximum) waiting times at stations and so on. A railway timetable can also be further constrained by specific demands of the services that are offered. For instance, a certain trajectory may require trains to travel with fixed intervals, or at least a number of times within a certain time frame (e.g. four times an hour). This is called a cyclic, or periodic railway timetable, which is known to be a special form of a Periodic Event Scheduling Problem (PESP). PESP is known to be NP-hard and therefore a challenge in itself even without the dynamic aspects [ Kees Pieters, "Computation in Complex Environments; Optimizing Railway Timetable Problems with Symbiotic Networks," Chapter 13 in Yoel Tenne and Chi-Keong Goh (Eds.). Computational Intelligence in Optimization: Applications and Implementations. Adaptation, Learning, and Optimization,Volume 7, Springer, 2009. ][Dario Pacciarelli and Marco Pranzo, "A Tabu Search Algortihm for the Railway Scheduling Problem, MIC’2001 - 4th Metaheuristics International Conference.].  
11
Flight Scheduling Problem: Given demand and revenues for every origin-destination pair over time-of-the-day and day-of-the-week, route information distances, times, operating restrictions, aircraft characteristics and operating costs and operational and managerial constraints. Find a set of flights with departure and arrival times and aircraft assignment which maximize profits. Ref. [Ghizlane Bencheikh, Jaouad Boukachour and Ahmed EL Hilali Alaoui, "Improved Ant Colony Algorithm to Solve the Aircraft Landing Problem," International Journal of Computer Theory and Engineering, Vol. 3, No. 2, April 2011 ISSN: 1793-8201] and [F. Mokhatab Rafiei, S.M. Manzari, M. Khashei, "Scheduling Flight Perturbations with Ant Colony Optimization Approach," International Journal of Computer Science and Artificial Intelligence ].

 

12
Crew Scheduling: is the process of assigning crews to operate transportation systems, such as rail lines or aircraft. In this problem, within a set of constraints and rules, move a set roster of people with certain qualifications, from place to place with the least amount of personnel and aircraft or vehicles in the least amount of time. Ref. [A. Azadeha, M. Hosseinabadi Farahania, H. Eivazyb, S. Nazari-Shirkouhia, G. Asadipoura, "A hybrid meta-heuristic algorithm for optimization of crew scheduling Applied Soft Computing, Volume 13, Issue 1, January 2013, Pages 158–164.], [Panta Lucica, Dusan Teodorovica, "Simulated annealing for the multi-objective aircrew rostering problem," Transportation Research Part A 33 (1999) 19-45] and [MING-SHEN JIAN, and TA-YUAN CHOU, "Multiobjective Genetic Algorithm to Solve the Train Crew Scheduling Problem," NEW ASPECTS of SYSTEMS THEORY and SCIENTIFIC COMPUTATION.].

 

13
University Course Timetabling Problem: Course Timetabling Problem is defined as: “a multi-dimensional assignment problem in which students, teachers (or faculty members) are assigned to courses, course sections or classes; events (individual meetings between students and teachers) are assigned to classrooms and times”. In university course timetabling, a set of courses is scheduled into a given number of rooms and timeslots within a week and, at the same time, students and teachers are assigned to courses so that the meetings can take place. The course timetabling problem is subject to a variety of hard and soft constraints. Hard constraints need to be satisfied in order to produce a feasible solution. hard constraints include, but are not limited to, No student can be assigned to more than one course at the same time. The room should satisfy the features required by the course. The number of students attending the course should be less than or equal to the capacity of the room. No more than one course is allowed to be assigned to a timeslot in each room. Soft constraints may include student has a course scheduled in the last timeslot of the day. A student has more than 2 consecutive courses. A student has a single course on a day [Salwani Abdullah, Edmund K. Burke, Barry McCollum, "Using a Randmonised Iterative Improvement Algorithm with Composite Neighbourhood Structures for the University Course Timetabling Problem", Chapter 8 in Metaheuristics Progress in Complex Systems Optimization, Springer, 2007] [Ruey-Maw Chen and Hsiao-Fang Shih, "Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search," Algorithms 2013, 6, 227-244; doi:10.3390/a6020227.].  
14
Timber Transport Vehicle Routing Problem (TTVRP): a heterogeneous fleet of m log-trucks that are situated at the respective homes of truck drivers must fulfill n transports of logs between various wood storage locations and industrial sites, such as pulp mills and sawmills, during a specified timeframe. All of the transports are carried out as full truckloads; the vehicle is loaded at the wood storage location and unloaded at the industrial site. Each route commences at the home of the truck driver who leaves with an empty truck for loading round timber. Subsequently, he drives to the designated industrial site and completes the transport. The truck driver can now finish his tour and return back home or start a new delivery. Due to the transportation orders, each wood storage location and industrial site can be visited more than once during the planning horizon. Log transport has a few specific constraints to consider such as the fact that some parts of the forest road networks are unsuitable for larger trucks, as their weight occasionally damages the road. Therefore, some wood storage locations can only be reached by trucks with a certain capacity. We denote this as the route weight limits. Due to industry operating hours, time windows for unloading wood must be considered. Time windows also occur at the truck starting points since truck drivers are only on duty at certain times. Additionally, we have to observe tour length constraints and capacity constraints. According to the given transportation orders, the objective is to minimize empty truck movements [Manfred Gronalt and Patrick Hirsch, "Log-truck Scheduling with a Tabu Search Strategy," Chapter 4 in Metaheuristics Progress in Complex Systems Optimization, Springer, 2007].  
15
Combinatorial Optimization in VLSI Design: chip is composed of basic elements, called cells, circuits, boxes, or modules. They usually have a rectangular shape, contain several transistors and internal connections, and have at least two pins (in addition to power supply). The pins have to be connected to certain pins of other cells by wires according to the netlist. A net is simply a set of pins that have to be connected, and the netlist is the set of all nets. The basic placement task is to place the cells legally "without overlaps" in the chip area. A feasible placement determines an instance of the routing problem, which consists of implementing all nets by wires. The quality of a placement depends on the quality of a wiring that can be achieved for this instance. For several reasons it is usually good if the wire length (the total length of the wires connecting the pins of a net) is as short as possible. [Ref.: Stephan Held, Bernhard Korte, Dieter Rautenbach, and Jens Vygen, "Combinatorial Optimization in VLSI Design"]  
16
Project Scheduling: Time-Cost Tradeoff Problems: The project manager handles conflicting states to optimize various parameters of project scheduling process. Minimizing project completion time and project cost continues to be universally sought objectives, conflicting in nature, which is known as time-cost tradeoff (TCT) in project scheduling. TCT belongs to a class of multiobjective optimization (MOO) problem wherein there is no single optimum solution rather there exists a number of solutions, which are all optimal – Paretooptimal solutions – optimal TCT profile in project scheduling literature. The tradeoff between project time and cost gives project managers both challenges and opportunities to work out the best schedule to complete a project, and is of considerable economic importance [Sanjay Srivastava, Bhupendra Pathak, and Kamal Srivastava, "Project Scheduling: Time-Cost Tradeoff Problems", Chapter 14 in Yoel Tenne and Chi-Keong Goh (Eds.). Computational Intelligence in Optimization: Applications and Implementations. Adaptation, Learning, and Optimization,Volume 7, Springer, 2009.]  
17
Reviewer Assignment for Scientific Articles: For the assignment of papers to referees, one should observe that each paper should be handled by the referees most competent for that paper. On the other hand, referees should get papers that lie in their area of interest, otherwise they would not be willing or able to review them. Finally, one should have a fair allocation of workload, i.e. all referees should receive approximately the same number of papers. Also, coauthors, the paper authors’ close friends or enemies, and maybe even their colleagues from the same institution or country should not be selected as referees. It is not straightforward how to capture all these aspects in a mathematical model. This problem can be viewed as an extension of the well-known generalized assignment problem (GAP) with additional constraints. GAP seeks a minimum cost or maximum profit assignment of n jobs to m agents subject to a resource constraint for each agent. In a GAP, each job is assigned to exactly one agent. In reviewer assignment problem, the task is to assign a defined number (in our case, 3) of best fitting reviewers to each paper while keeping the workload distribution fair, i.e. balanced [Alexander Schirrer, Karl F. Doerner and Richard F. Hartl, "Reveiwer Assignment for Scientific Articles using Memetic Algorithms," Chapter 6 in Metaheuristics Progress in Complex Systems Optimization, Springer, 2007].  
18
Political Districting Problem: is defined as aggregating n sub-regions of a territory into m electoral districts subject to the following constraints: 1. The districts should have near-equal voting population, 2. The socio-economic homogeneity inside each district as well as the integrity of different communities should be maximized, 3. The districts have to be compact and the sub-regions of each district have to be contiguous and 4. Sub-regions should be considered as indivisible political units and their boundaries should be respected. Ref. [Burcin Bozkaya, Erhan Erkut, Gilbert Laporte, "A tabu search heuristic and adaptive memory procedure for political districting European Journal of Operational Research 144 (2003) 12-26] and [Sean L. Forman and Yading Yue, "Congressional Districting Using a TSP-Based Genetic Algorithm"].

 

19
Supply Chain Optimization: The supply chain encompasses all activities associated with the flow and transformation of goods from raw material stages through to the end users, as well as the associated information flows. Material and information both flow up and down on the supply chain. A supply chain consists basically on the following elements: suppliers, manufacturing centers, warehouses, distribution centers, transportation systems, retail outlets and customers; raw material, work-in process inventory, finished goods and information that flow between the different elements. The supply chain is a complex network of facilities and organizations with interconnected activities but different and conflicting objectives. Many companies are interested in analyzing their supply chain as an entire and unique system to be able to improve their business. However, in most cases the task of designing, analyzing and managing the supply chain has been done based on experience and intuition; very few analytical models and design tools have been used in the process. This implies that finding the best supply chain strategies for a particular firm, group of firms or sector poses significant challenges to the industry and academia. Metaheuristics can be an important tool of helping managers and consultants in the decision process [Ref.: Helena R. Lourenço, "Supply Chain Management: An opportunity for Metaheuristics"]. 
20
Optimizing Ride Share Apps: Ride Share apps such as Uber, Lyft, Sidecar and RideCo have two main goals: getting you a ride when you need it and maximizing trips taken on the system, which maximizes driver partners’ earnings. Fulfilling these goals requires modeling a number of complex, non-linear, interacting systems. During slow hours, drivers are willing to pick up a passenger who’s far away. If it’s super busy, drivers are less likely to accept trips with longer pickup times…since they figure they’ll get a closer request if they wait a few more minutes.). This knowledge can be used to generate plausible optimizations for the ride share apps [Ref.: http://blog.uber.com/aisimulation].
21
Design of Global Navigation Satellite System Surveying (GNSS) Networks: A GNSS is a space-based satellite system which provides coverage for all locations worldwide and is quite crucial in real-life applications such as early warning and management for disasters, environment and agriculture monitoring, etc. The goal of surveying is to determine the geographical positions of unknown points on and above the earth using satellite equipment. These points, on which receivers are placed, are co-ordinated by a series of observation sessions. When there are multiple receivers or multiple working periods, the problem of finding the best order of sessions for the receivers can be formulated as an mTSP. For technical details refer [Saleh, H.A. & Chelouah, R. (2004). The design of the global navigation satellite system surveying networks using genetic algorithms. Engineering Applications of Artificial Intelligence, Vol. 17, pp. 111–22.].  
22
Camera Placement for Airport Surveillance: Multi-sensor surveillance systems are used to monitor or observe the behaviour of persons, processes, places, objects, etc. to determine whether they are functioning normally or if there is any deviation from their standard behaviour. These systems include a vast array of static and mobile sensors. Static sensors include, but not limited to, light sensors, temperature sensors, perimeter intrusion detector, sound sensors, fire detectors and cameras. Static sensor placement has an enormous impact on the performance of the surveillance system. Static sensor placement problem can be seen as a combinatorial problem that involves the placement of a set of N sensors with different fields of view in a set of M areas of interest. Suggested reading [Mohammad Reza Shams Amiri. Automated Camera Placement using Hybrid Particle Swarm Optimization. European Master in Computer Science, Blekinge Institute of Technology, 2014] and [N. Conci and L. Lizzi, "CAMERA PLACEMENT USING PARTICLE SWARM OPTIMIZATION IN VISUAL SURVEILLANCE APPLICATIONS", ICIP 2009].  
23
Robot Path Planning Problem: This problem is an interesting problem that has been studied extensively over the last two decades. This problem addresses how to find a collision-free path for a mobile robot from a start position to a given goal position, amidst a collection of obstacles. Path planning can be seen as an optimization problem which aims at improving some system objectives with several constraints. System objectives may be the travelling distance, travelling time, and consuming energy. However, the travelling distance is the most common objective. Beside this, the necessity of considering collisions avoidance and path smoothness makes the problem becoming more challenging. Ref. [Yun-Qian Miao Miao, Alaa Khamis, Mohamed Kamel, Fakhri Karray, “A Novel Approach to Path Planning for Autonomous Mobile Robots”, Journal of Control and Intelligent Systems, 2011.], [Yun-Qian Miao, Alaa Khamis, Mohamed Kamel, Fakhri Karray, "Global Optimal Path Planning for Mobile Robots based on Hybrid Approach with High Diversity and Memorization," International Conference on Autonomous and Intelligent Systems (AIS 2011), June 22-24, 2011, Burnaby, BC, Canada] and [H. Mostafa, A. Hussein, M. Badrel-din, O. Sultan and A. Khamis, “Metaheuristic Optimization Approach to Mobile Robot Path Planning”, International Conference on Engineering and Technology (ICET2012), New Cairo, 2012].  
24
Unmanned Aerial Vehicle Routing Problem: The vehicle routing problem (VRP) is a combinatorial optimization problem that determines a set of minimum cost routes from one or multiple depots for a fleet of homogeneous vehicles to service a set of geographically scatter customers. Vehicles are dispatched from a depot to deliver goods or services, and then return back to the depot. Each route starts and ends at the same depot, all customers are visited exactly once, and the total demand of customers in a route must not exceed the vehicle capacity. In practice, the objective is equivalent to minimizing a total traveling distance, or minimizing a total number of vehicles used. Because of the nature of Unmanned Aerial Vehicle (UAV) applications, a UAV operation is often disrupted and long range communications between UAVs and their base are very difficult. Consequently, most UAV routing plans are static and predetermined before the operation starts. In addition, UAV operations are vulnerable to uncertainties. For example, in military applications, risks in UAV operations include a probability of being shot down, and stochastic targets. In scientific applications, risks include mechanical failures, and infeasible routes due to increment weather. From these reasons UAV routing is very uncertain and requires an efficient solution method that not only find optimal routing plan but also controls variations in a UAV operation. According to literature, UAV routing problem is normally modeled as a traditional vehicle routing problem where side constraints will be added to reflect natures of applications. In realistic UAV routing, UAVs must visit their targets within their specified time windows. This means that a UAV must increase its air speed in order to maintain its scheduled ground speed when it flies a route with stronger head wind. In contrast, a UAV can decrease its air speed in order to maintain its scheduled ground speed and save its fuel. Efficiently choosing routes can significantly reduce the total amount of fuel burn a UAV consumes to visit all of its targets [SIRIWAT VISOLDILOKPUN. UNMANNED AERIAL VEHICLE ROUTING PROBLEM WITH LIMITED RISK. PhD Thesis, THE UNIVERSITY OF TEXAS AT ARLINGTON, 2008].  
25
Static Waypoint Ordering Problem of Unmanned Vehicles: A basic tool needed by an unmanned vehicle system (UVS) operator is a way of generating the trajectory of a vehicle automatically one he/she has specified a set of target locations that the vehicle must inspect. Often, the order in which the sites are to be inspected is no specified a priori and we should design the tour of minimum length visiting the waypoints, of equivalently the minimum time tour if the velocity of the vehicle is constant. Gains in performance on this problem can have a large impact since the tour might have to be executed repetitively during the duration of a surveillance mission. It is also a building block for static scheduling policies where, once an order of the waypoints has been chosen to minimize the total travel time, we can specify the time to spend at each site for inspection. Static waypoint ordering problem is the problem of minimizing the travel distance of an unmanned vehicle with differential constraints. These vehicles are called Dubins vehicle such as fixed wing UAVs). Dubin vehicle can only move forward in the place, at constant speed, and has a limited turning radius [H. Ny. Performance Optimization for Unmanned Vehicle Systems. PhD. Thesis, MIT, 2008.].  
26
Complex Task Allocation Problem: In mobile surveillance systems, complex task allocation addresses how to optimally assign a set of surveillance tasks to a set of mobile sensing agents to maximize overall expected performance, taking into account the priorities of the tasks and the skill ratings of the mobile sensors. Ref. Alaa Khamis, Ahmed Elmogy and Fakhreddine Karray, "Complex Task Allocation in Mobile Surveillance Systems," Journal of Intelligent and Robotic Systems, Springer], [Mohamed Badreldin, Ahmed Hussein and Alaa Khamis, "A Comparative Study between Optimization and Market-based Approaches to Multi-robot Task Allocation," Advances in Artificial Intelligence Journal, 2013.] and [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014].  
27
Multiple Targets Clustering Problem: Clustering in a d-dimensional Euclidean space is the process of partitioning a given set of n points into a number, say k, of groups (or clusters) based on some similarity metric between objects. Suppose that it is required to track n targets using k mobile trackers. If the number of available trackers is less than the number of targets to be tracked, the targets can be grouped into a number of clusters equal to the number of trackers. Then the tracker can track the centroid of the cluster instead of the target itself. This clustering process is based on the positions of targets. Ref. [Ujjwal Maulik, Sanghamitra Bandyopadhyay, "Genetic algorithm-based clustering technique", Pattern Recognition 33 (2000)1455-1465.].  
28
Multirobot Control: Unintelligent carts are commonly found in large airports. Travelers pick up carts at designated points and leave them in arbitrary places. It is a considerable task to re-collect them. It is, therefore, desirable that intelligent carts (intelligent robots) draw themselves together automatically. Using mobile software agents to locate robots scattered in a field, e.g. an airport, and make them autonomously. The objective is to determine the moving behaviors of smart carts by using an metaheuristic optimization-based clustering algorithm. Resources must be used efficiently to maximize the benefit of utilizing a multirobot team. For example, in search and rescue time is of the utmost importance, while for planetary exploration fuel efficiency may be a primary concern. Ref. [Yasushi Kambayashi, Yasuhiro Tsujimura, Hidemi Yamachi, Munehiro Takimoto and Hisashi Yamamoto, “Design of a Multi-Robot System Using Mobile Agents with Ant Colony Clustering”, Proceedings of the 42nd Hawaii International Conference on System Sciences – 2009][Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014]  
29
Collective Robotic Search (CRS): A group of unmanned mobile robots are searching for a specified target in a high risk environment. Assumptions: A number of robots/particles are randomly dropped into a specified area and flown through the search space with one new position calculated for each particle per iteration; The coordinates of the target are known and the robots use a fitness function, in this case the Euclidean distance of the individual robots relative to the target, to analyze the status of their current position; Obstacle's boundary coordinates are known. Ref. [Smith, L., Venayagamoorthy, G. K. and Holloway, P. (2006): Obstacle Avoidance in Collective Robotic Search Using Particle Swarm Optimization. IEEE Swarm Intelligence Symposium, Indianapolis, Indiana, USA, May 2006.], [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014] and [Qing-Hao Meng, Wei-Xing Yang, Yang Wang, Ming Zeng, " Multi-robot odor-plume tracing in indoor natural airflow environments using an improved ACO algorithm 2010 IEEE International Conference on Robotics and Biomimetics (ROBIO), 2010.]  
30
Communication Relay for Unmanned Aerial Vehicles in Autonomous Search and Rescue Mission: The objective of this project is to simulate search and rescue scenarios where autonomous unmanned aerial vehicles are deployed to locate multiple rescue targets. When a target is found, the swarm of micro-aerial vehicles (MAVs) self-organizes to utilize their range-limited communication capabilities for setting up a communication relay network between the target and the base. This solution is appropriate for real-world situations where rescue targets are trapped on intraversable terrain with a limited radius of communication. Ref. [Sabine Hauert, Laurent Winkler, Jean-Christophe Zufferey and Dario Floreano, "Ant-based swarming with positionless micro air vehicles for communication relay," Swarm Intell (2008) 2: 167–188], [Wave Relay MANET Communication System Connects Swarming Unmanned Aerial Vehicles Persistent Systems, LLC, 2007] and [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014].  
31
Trajectory Planning and Assignment in Multirobot Systems: This problem addresses tasking large numbers of homogenous robots to move to a set of specified goal locations, addressing both the assignment and trajectory planning subproblems concurrently. This is related to the standard linear Euclidean assignment problem except that the solution to the trajectory generation subproblem must result in time-parameterized trajectories and guarantee collision avoidance.. Ref. [Matthew Turpin, Nathan Michael, and Vijay Kumar, "Trajectory Planning and Assignment in Multirobot Systems,"Algorithmic Foundations of Robotics X, Springer Tracts in Advanced Robotics Volume 86, 2013, pp 175-190].), and [Alaa Khamis, Cooperative Multirobot Systems, Plenary Talk at IAC2014].  
32
Design/Research Problem: Identify a combinatorial design/research problem in a pertinent area of academic, industrial or commercial importance for which there is no available solution with reasonable capabilities. Try to solve this problem using one of metaheuristic techniques studied in this course. Students can also select a problem related to their Engineering Design Project course where the studied metaheuristic techniques can be applied. Important Note: Instructor’s approval is required for this option. Please send brief description of your suggested project problem to the course instructor before the project seelction deadline for his review and approval.]

Project Work Plan: a suggested work plan for the project can be downloaded here ECE457A-Project.pdf.


Project Report: 

The objective of the final project is to provide a comparative study between different meta-heuristic optimization techniques to solve the selected problem. The project report must contain the following sections: 

Summary: The Summary should be a brief version of the full report. It should give the reader an accurate overview. Be brief, but be specific. 

1. Introduction: summarize the importance of the problem you are trying to solve and the reason that motivated you to select this project. Explain what was the problem or challenge that you were given? state the purpose of the project and how did you solve it? Enumerate the objectives of the project and describe in brief the structure of the report. 

2. Literature Review: Conduct a critical survey on similar solutions and explain how your solution extends or differs from these solutions. 

3. Problem Formulation and Modeling: Include the problem statement and describe its model.

4. Proposed Solution:

  • Generate an initial solution.
  • Suggest a cost function (objective function) suitable for this problem.
  • Define a suitable neighborhood operator.
  • Define a suitable solving strategy for this problem.
  • Select your own values for the parameter and explain the basis for your selection.
  • Describe how each algorithm (TS, SA, GA, PSO and ACO [and optionally one of the self-study algorithms]) will proceed to solve this problem by performing at least two hand iterations on a reduced version of the problem.
  • Implement the proposed solution using Matlab/Octave.
5. Performance Evaluation: Establish a set of evaluation metrics and run some experiments with different values of algorithm parameters to quantitatively and qualitatively assess the performance of the developed solution using different meta-heuristic optimization techniques. Students must identify the pros and cons of each technique and assess the quality of work as well as its fit with project objectives.

6. Conclusions & Recommendations: summarize the conclusion and future improvement. Explain how did you solve the problem, what problems were met? what did the results show? And how to refine the proposed solution?You may organize ideas using lists or numbered points, if appropriate, but avoid making your report into a check-list or a series of encrypted notes 

References: Every report needs references; in fact, your failure to consult references for guidance may be considered negligence. On the other hand, when you include sentences, photos, drawings or figures from other sources in your report, the complete reference must be cited. Failure to do so is plagiarism, an academic infraction with serious consequences.


Project Delivery: 

In order to complete evaluating the project, each team has to submit the project material by July 24, 2015. Please Zip the project material and name it "Your Project Number#.zip" and upload it to “Project” dropbox on LEARN. The Zip file should include all materials related to the project (final course project report [Word/Latex] according to the course policy + a well documented Matlab/Octave code with ReadMe/UserGuide that shows how to use the developed software).