Review problems for Midterm Exam $2$:

Clara Belle is planning a road trip through Europe. She plans to visit Frankfort, Zurich, Vienna,

Budapest, Prague, and Paris. The estimated distances between these cities are provided in the

table below.

From$/$To Frankfort Zurich Vienna Budapest Prague Paris

Frankfort $0250440600320350$

Zurich $0450600420400$

Vienna $0150180770$

Budapest $0320920$

Prague $0640$

Paris $0$

$1-$ Use Chritofide$$s heuristic to find a route for her tip.

$2$

$2-$ Use Nearest Neighbor heuristic to find a route for her trip.

$3$

$3-$ If you were to use the cheapest insertion heuristic to find a route for her trip what would

be the insertion cost of visiting Budapest between Vienna and Prague.

$4$

She needs to take a set of $15$ items with the following weights $($in lbs$)$ with her: $4,5,8,7,8,12,$

$13,4,10\mathrm{.}5,3\mathrm{.}5,6,7,5,18,2.$ The airline has a $40$lb weight limit for the luggage and charges

$$25$ for the first bag, $$35$ for the second bag, and $$50$ for any additional bags. What would be her

luggage cost if she uses the following algorithms:

$4-$ Next$-$fit:

$5-$ First$-$fit:

$5$

$6-$ Best$-$fit:

$7-$ Next$-$fit Decreasing:

$6$

$8-$ First$-$fit Decreasing:

$9-$ Best$-$fit Decreasing:

$7$

$10-$ What is the theoretical minimum number of bags she needs to fit all her items?

$8$

$11-$ Use Sweep heuristic to find optimum delivery routes for trucks of capacity $100$ ft$3$ located

at a warehouse with coordinates $(0,0),$ serving the following set of customers. Use X axis

as your starting ray.

Customer X$-$coordinate Y$-$coordinate Demand

$10646$

$2-4432$

$35155$

$43540$

$5-3-2100$

$64-570$