Mobile Facility Routing Problem With Visit Constraint And Time-dependent Demand

FLP is an old topic. While with the development of technology and service level,mobile facilities emerge. They can be used in many applications.Mobile Facility Routing Problem(MFRP) seeks to create routs for mobile facilitiesthat maximize the demand serviced by these facilities. This thesis study on MFRP withvisit constraint and time-dependent demand (MFRP-VCTD),basically on fairness.Through relaxation of some constraints, MFRP-VCTD can be changed to VRP orFLP. Since VRP and FLP is NP-hard, MFRP-VCTD is also NP-hard. We directlyformulate MFRP-VCTD as a Nonlinear Model. To solve the problem, we use timediscretization and approximately formulate it as MIP. It is difficult to solve reasonablesize of this problem, but we can use ILOG cplex to solve small data size problem.To solve reasonable data size of MFRP-VCTD, we design a heuristic to createroute for mobile facilities. Starting from single mobile facility routing problem, we canchange this problem into finding the longest path in DAG. Then we add constraints stepby step: min-service time, visit once, fairness. We extend single mobile facilityalgorithm to multiple mobile facilities. In addition, an improvement algorithm is appliedto improve the performance of heuristic.In order to evaluate the effectiveness of heuristic we developed a variety ofsimulated data sets. There are two parts of the data sets. Small data size and reasonabledata size. For small data size, we compare results obtained by MIP and heuristic, findingthat results generated by our heuristic were competitive. To better evaluate our heuristic,we change time-dependent demand to static demand since it could compute problemwith larger size. A comparison of heuristic and static demand problem also shows thatour heuristic performs well. For the reasonable data size, our heuristic can get the resultsquickly. As a result, we should choose heuristic to solve reasonable size problem.We formulate a time-discretized MIP of this problem. We present heuristic forrouting mobile facilities to maximize amount of demand serviced. Our computationalresults confirm the effectiveness of our heuristic. In future research, uncertain demandcan be considered and a method for solving reasonable data size MFRP would be useful.