A serious proposal as well as an opportunity for critical thinking: What holes or objections can readers identify?
Proportional representation eliminates gerrymandering by treating the whole state as one district and assigning multiple seats in that state according to the proportion of the vote gained by a given party. But let me put aside that possibility and stay with the traditional subdivision of a state into districts. Here is a way to do re-districting without gerrymandering and to reduce risk that votes for one party will be concentrated into a few districts.
(This method also has the virtue that everyone in a district at any level (e.g., state representatives) will be in same district at levels above that (e.g., state senate and federal house. See #5 for a possible exception .)
1. Set the maximum deviation of a political district from average population size for a political district in that state, say 2%.
2. Consider the smallest units, precincts in a town or city.
a. Aggregate those units into the number of state representative districts. (The aggregation method could be something like: i. from all the units in the state, randomly choose a first unit for all the districts (where units with larger populations are more likely to get chosen); ii. Add a unit to each randomly from any contiguous units remaining available. Repeat ii until all units are assigned to a district. [A variant of ii more likely to arrive at comparable sized districts might add a unit from the direction furthest away from other districts.])
b. If any districts deviate from the average more than the maximum, reject that districting map and return to a. If OK, then calculate i. the miles along the perimeter/area for each district and average those; and ii. the % decline in seats that would be won by the largest party if the vote were to swing 1% against them in every unit. (If 0%, then calculate with a swing of 2%, and so on.)
c. Repeat a. until 100 OK maps. Choose 10 with lowest perimeter/area average. Choose 10 with largest % shift. If any maps are in both sets, select those as the basis for step 3. If no map is in both sets, expand out to 11 of each, and so on. (This method may need to be fine-tuned through simulations in order to arrive at a procedure that best reduces the risk that votes for one party will be concentrated into a few districts. It may be that perimeter/area is less important than % shift.)
3. For each of those selected maps from 2, repeat the same steps, but this time with units being state representative districts and aggregated into the number of state senate districts. Of the OK maps, follow step c.
4. For each of the selected maps, repeat the same steps, but this time with units being state senate districts aggregated into the number of federal representative districts. If there is more than one map emerging from steps 2-4, choose the one with the largest % decline in seats that would be won by the largest party if the vote were to swing 1% against them in every unit. (This reduces the risk that votes for one party will be concentrated into a few districts.)
5. It is possible that the three levels of districting do not nest into each other without large deviations from the average population size. In that case, allow the largest district at one level to be split into two different districts for the purposes of aggregating then at next level. Repeat for next largest district until maps emerge that do not exceed the maximum deviation from the average population.
6. The first time this method is used the districts will diverge greatly from the existing districts. But once they are established future redistricting can use them as a basis. Random reassignments of units from one district to a contiguous one could be tested to see if a map could be produced that better fulfills the criteria of comparable population, low perimeter/area, and swingableness.